说明课堂演示2013dm

1、第十章 树与有序树10.1 树的基本概念树的基本概念10.2 连通图的生成树和带权连通图的连通图的生成树和带权连通图的最小生成树最小生成树 10.3 有序树有序树10.4 前缀码和最优二分树前缀码和最优二分树 英文的编码通信英文的编码通信英文的编码通信中，考察用英文的编码通信中，考察用0和和1来表示英文字母的问来表示英文字母的问题，因为字母表中的题，因为字母表中的26个字母必须用个字母必须用0和和1组成的序列组成的序列来表示，故它们可以用长度为来表示，故它们可以用长度为5位位(因因 242625)的序列的序列表示出来。表示出来。要传递一条信息，我们只要传递用来表示消息而组成要传递一条信息，我们

2、只要传递用来表示消息而组成字母序列的一个字母序列的一个0、1字符串即可。在接收端，把这一字符串即可。在接收端，把这一0、1字符串分为长度为字符串分为长度为5位的序列，而这些序列对应位的序列，而这些序列对应的字母就可以识别出来。的字母就可以识别出来。英文字母使用频数英文字母使用频数数串划分问题数串划分问题当用各种不同长度的序列来表示字母时，在接收端当用各种不同长度的序列来表示字母时，在接收端，就存在如何把一个，就存在如何把一个0、1的数串划分为对应字母序的数串划分为对应字母序列的问题？列的问题？例如，如果例如，如果 00=e 01=t 0001=w 那么那么 0001=?前缀码前缀码序列序列 a

3、1a2am 是序列是序列 b1b2bmbm+1bn的前缀，如的前缀，如果果 a1a2am=b1b2bm。对于序列的一个集合来说，若这个集合中的任何序列对于序列的一个集合来说，若这个集合中的任何序列都不是另一个序列的前缀，则这个集合称为前缀码。都不是另一个序列的前缀，则这个集合称为前缀码。例例 000, 001, 01, 10, 11 是一个前缀码是一个前缀码 1, 00, 01, 000, 0001 不是一个前缀码不是一个前缀码 0001=00+01?0001=000+1?0001=0001?2分树分树 前缀码前缀码由任何一棵由任何一棵2分树可以得到一个前缀码，且对应一分树可以得到一个前缀码，

4、且对应一个前缀码也一定存在一棵相应的个前缀码也一定存在一棵相应的2-分树。分树。 例例 10, 001, 010, 011,110 为一个前缀码。为一个前缀码。前缀码前缀码 2分树分树例例 前缀码前缀码01,10,001,110 所对应的一棵所对应的一棵2分树。分树。001 110 10 01 (b) 000 00 1 010 011 100 101 110 111 0 0 0 0 00 0 0 0 1 1 1 1 11 10 1 1 1 0 01 (a) 字符串 前缀码中的码字例例: 已知前缀码如下图已知前缀码如下图试划分下述字符串试划分下述字符串: 10一段英文所用的字符串的平均长度一段英

5、文所用的字符串的平均长度假设在假设在N个英文字母组成的短文中，英文第个英文字母组成的短文中，英文第 i个字母个字母出现的频率是出现的频率是 wi次，而第次，而第 i个字母用个字母用Li长的长的0和和1序列序列来表示，则来表示，则N个英文字母组成的一段英文所用的字个英文字母组成的一段英文所用的字符串的平均长度为符串的平均长度为 261ii261ii2626221121 Lw LNNiiNNLNLNLNNAAA2分树的叶子权分树的叶子权假如我们有一组权假如我们有一组权w1,w2,wnw1,w2,wn。不失一般性，。不失一般性，设设 0w1w2 wn 0w1w2 wn一棵有一棵有n n片叶子的片叶子

6、的2 2分树，如果分配给它的叶分树，如果分配给它的叶子的权分别为子的权分别为w1,w2,wnw1,w2,wn，则这棵则这棵2 2分树称为叶子权为分树称为叶子权为 w1,w2,wn w1,w2,wn的的2 2分树。分树。2 2分树分树T T的权的权W(T)W(T)定义叶子权为定义叶子权为 w1,w2,wn w1,w2,wn的的2 2分树的权分树的权W(T)W(T)为为: : W(T) = wiL(wi) W(T) = wiL(wi)，其中其中L(wi) L(wi) 是具有权为是具有权为wiwi的叶子的路长。的叶子的路长。例例 构造权值分别构造权值分别为为7,5,2,4的二的二叉树叉树abcd75

7、247*2+5*2+2*2+4*2=367*3+5*3+2*1+4*2=46abcd75247*1+5*2+2*3+4*3=35dcab2475最优树最优树在叶子权为在叶子权为w1,w2,wn的所有的所有2分树中，具有最小分树中，具有最小权的一棵权的一棵2分树，称为最优树。分树，称为最优树。12+14+33=5960例例霍夫曼(Huffman D.A)算法 指导思想指导思想: 把求带把求带n个权的最优树变为求带个权的最优树变为求带n-1个权的个权的最优树。最优树。命题命题1存在一棵带权存在一棵带权w1,w2,wn的最优的最优2分树，而且带分树，而且带权权w1和和w2的二片叶子是兄弟。的二片叶子

8、是兄弟。a awx wya aw1 w2命题1的证明显然带权显然带权w1,w2,wn的最优的最优2分树一定存在。设分树一定存在。设T是一棵这是一棵这样的样的2分树。分树。a是是T中通路最长的分支点。中通路最长的分支点。a的两个儿子的两个儿子a1和和a2分别带权分别带权wx和和wy。由于由于T是最优的，所以每一个分枝点都有两个儿子，否则这个是最优的，所以每一个分枝点都有两个儿子，否则这个分枝点可以去掉，让它的儿子代替它，仍是一个带权的分枝点可以去掉，让它的儿子代替它，仍是一个带权的2分分树，但树的权减少了。树，但树的权减少了。设设wxwy，则有，则有w1wx，w2wy。让。让a1带权带权w1，让

9、带权，让带权w1的的叶子带权叶子带权wx，a2带权带权w2，带权，带权w2的叶子带权的叶子带权wy，我们得到一，我们得到一棵新的带权棵新的带权w1,w2,wn的的2分树，设为分树，设为T。显然，。显然， L(wx)L(w1)，L(wy) L(w2)，所以，所以，W(T)W(T)。由于是最优的，所以。由于是最优的，所以W(T)=W(T)，而，而T是一棵带权最优是一棵带权最优2分树且带权分树且带权w1与与w2的两片叶子是兄弟的两片叶子是兄弟。命题1的意义从一棵带权最优二分树，一定可以得到一棵带权最小从一棵带权最优二分树，一定可以得到一棵带权最小的两片叶子是兄弟的最优树。所以，可以设的两片叶子是兄弟

10、的最优树。所以，可以设T是一棵是一棵带权带权w1,w2,wn的最优树，且带权的最优树，且带权w1和和w2的两片叶的两片叶子是兄弟。子是兄弟。把带权把带权w1和和w2的两片叶子去掉，让他们的父亲变成的两片叶子去掉，让他们的父亲变成一片叶子带权一片叶子带权w1+w2，这时我们得到一棵带权，这时我们得到一棵带权w1+w2 w3,w4,wn的的2分树，记为分树，记为 T。显然有显然有 W(T)=W(T)-w1-w2。权权w1+w2的路长少了的路长少了1命题2 设设T是一棵带权是一棵带权w1+w2 w3,wn的最优树，将的最优树，将带权带权w1+w2的叶子变为分枝点，让它的两个儿的叶子变为分枝点，让它的

11、两个儿子分别带权子分别带权w1和和w2得一棵带权得一棵带权w1,w2,w3,wn的的2分树，记为分树，记为T。 T也是最优树。也是最优树。a aw1 w2a aw1+w2命题2的证明 由已知由已知, 显然有显然有 W(T)=W(T)+ w1+w2。若若T不是最优树，设不是最优树，设T*是一棵带权是一棵带权w1,w2,wn的最的最优树且优树且W(T*)W(T), 且带权且带权w1和和w2的两片叶子是兄的两片叶子是兄弟。从弟。从T*可以得到一个带权可以得到一个带权w1+w2 w3,wn 的的2分树分树T*，且有，且有W(T*)=W(T*)-w1-w2。因为因为T是带权是带权w1+w2 w3,wn的

12、最优树，所以的最优树，所以W(T)W(T*)=W(T*)-w1-w2 于是，有：于是，有：W(T)=W(T)+w1+w2W(T*)这与假设这与假设W(T*)W(T)矛盾。矛盾说明矛盾。矛盾说明T是最优树。是最优树。例例 求带权求带权2,3,5,7,10最优最优2分树。分树。分析：等于构造分析：等于构造5，5，7，10的最优树；的最优树； 等于构造等于构造7，10，10的最优树；的最优树； 等于构造等于构造10，17的最优树。的最优树。哈夫曼树的构造步骤哈夫曼树的构造步骤1) 根据给定的根据给定的n个权值个权值 ，构造，构造n棵只有一个根结点的棵只有一个根结点的二叉树，二叉树， n个权值分别是这

13、些二叉树根结点的权。个权值分别是这些二叉树根结点的权。设设F是由这是由这n棵二叉树构成的集合。棵二叉树构成的集合。2) 在在F中选取两棵根结点树值最小的树作为左、右子中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和。左、右子树根结点权值之和。3) 从从F中删除这两颗树，并将新树加入中删除这两颗树，并将新树加入F。4) 重复重复 2) 和和3)，直到，直到F中只含一颗树为止。中只含一颗树为止。例例 w=5, 29, 7, 8, 14, 23, 3, 11，求哈夫曼树，求哈夫曼树514297823

14、31114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100例例 最优判定问题最优判定问题等级分数段比例ABCDE059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70BACDE2755154030105*1+15*2+40*3+30*4+10*4

15、=275EADBC20540301551040*1+30*2+15*3+5*4+10*4=205哈夫曼树哈夫曼树例子例子例例 某通讯系统只使用某通讯系统只使用8种字符种字符a、b、c、d、e、f、g、h，其，其使用频率分别为使用频率分别为0.05,0.29,0.07,0.08, 0.14,0.23, 0.03,0.11。构造以字符使用频率作为权值的哈夫曼树。将权值取为整构造以字符使用频率作为权值的哈夫曼树。将权值取为整数数w=(5,29,7,8,14,23,3,11)，按哈夫曼算法构造的一棵哈夫，按哈夫曼算法构造的一棵哈夫曼树如下：曼树如下：对应字符的编码对应字符的编码a: 0110b: 10

16、c: 1110d: 1111e: 110f: 00g: 0111h: 0101）构造以）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉树；为叶子结点的二叉树；2）将该二叉树所有左分枝标记）将该二叉树所有左分枝标记1，所有右分枝标记，所有右分枝标记0；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929abecdfhg哈夫曼编码平均码长与平均压缩率哈夫曼编码平均码长与平均压缩率a: 0110b: 10c:

17、 1110d: 1111e: 110f: 00g: 0111h: 010平均码长=4*(5%+7%+8%+3%) +3*(14%+11%) +2*(29%+23%) =2.71292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929abecdfhg若用这三位二进制数(07)对这8个字母进行等长编码, 等长编码的长度为3。于是，哈夫曼编码的平均压缩为： 2.7131-=1-90.3%=9.7%例给定权为给定权为 1，4，9，16，25，36，49，64，87，100。构造一棵带权最优构造一棵带权最优3-分树分树(三叉树三叉树)。

18、解解:1491625364964871001455140251?例给定权为给定权为 1，4，9，16，25，36，49，64，87，100。构造一棵带权最优构造一棵带权最优3-分树分树(三叉树三叉树)。解解:014916253649648753091200100391构造一棵最优 t叉树（1）首先找出）首先找出 t个最小的权值，然后对这个最小的权值，然后对这t个权值构造个权值构造出一个出一个t叉树，并对该叉树，并对该t叉树的树根置权值为叉树的树根置权值为t个个最小权值之和。依此类推，由构造过程可知，最小权值之和。依此类推，由构造过程可知，除根外其它分支点恰有除根外其它分支点恰有t个儿子。个儿子

19、。（2）如果构造出来的树跟恰好有）如果构造出来的树跟恰好有 t个儿子，那么这棵个儿子，那么这棵树就是最优树就是最优t叉树。如果构造出来的树根的儿子叉树。如果构造出来的树根的儿子数目数目kt ，那么在原来的权值中添加，那么在原来的权值中添加 (t-k) 个个0，按照步骤按照步骤(1)重新构造重新构造 t叉树，它能保证每个分支叉树，它能保证每个分支点都有点都有t 个儿子，这是最优个儿子，这是最优 t叉树。叉树。Huffman coding In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a