树和二叉树(5哈夫曼树及其应用).ppt

《树和二叉树(5哈夫曼树及其应用).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6.6哈夫曼树及其应用1.相关概念路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。如结点A到结点F的路径为：A-B-E-FABCDEFG6.6.1最优二叉树路径长度：路径上面的分支个数。如A-F的路径长度为3。ABCDEFG树的路径长度：从树根到每一个结点的路径长度之和。如左边树的路径长度为：Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G)=1+1+2+2+3+3=12ABCDEFG结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数

2、值通常称为该结点的权值，简称权。如左图。ABCDEFG412537结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。如结点E的带权路径长度为:Len(E-A)*3=2*3=6ABCDEFG412537树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：WPL=w1*L1+w2*L2+……+wn*LnABCDEFGw1w2w3w4最优二叉树（哈夫曼树）：给定n个权值{w1,w2,…,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WP

3、L最小的二叉树称作最优二叉树或者哈夫曼树。ABCDEFGw1w2w3w42.哈夫曼算法（1）如何构造一棵哈夫曼树。我们首先通过一个例子来演示一下构造过程。当权值为{7，5，2，4}时，构造哈夫曼树。7524当权值为{7，5，2，4}时，构造哈夫曼树。75246当权值为{7，5，2，4}时，构造哈夫曼树。72465当权值为{7，5，2，4}时，构造哈夫曼树。7246511当权值为{7，5，2，4}时，构造哈夫曼树。7246511当权值为{7，5，2，4}时，构造哈夫曼树。724651118（2）哈夫曼算法的语言描述根据给定的n个

4、权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复②和③，直到F只含一棵树为止。这棵树便是哈夫曼树。6.6.2哈夫曼编码对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。现在要对字符串进行0、1编码，有哪些

5、方法？哪一种编码的长度最短？1.各种编码方式（1）定长编码---根据出现的字符种数进行编码字符串“ABACCDA”中共出现4种字符，那么可以用2位表示。ABCD00011011那么字符串“ABACCDA”的编码将为“00010010101100”，总长度为7*2=14位1.各种编码方式（1）定长编码---根据出现的字符种数进行编码这种编码方式可以对应到二叉树，如右图所式ABCD00011011ABCD0001111.各种编码方式（2）变长编码当A、B、C、D按照如下形式进行编码时。ABCD011010111那么字符串“ABAC

6、CDA”的编码将为“0110010101110”，总长度为13位，比第二种方式又要短。采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。1.各种编码方式（2）变长编码这种编码方式也可以对应到二叉树，如右图所式ABCD011010111ABC0011D011.各种编码方式（2）变长编码如当A、B、C、D按照如下形式进行编码时。ABCD01101111请将“0111”翻译成字符串。试一试，有哪些翻译方式。之所以会出现二义性，是因为出现了A的编码是C的编码的前缀；B的编码是

7、D的编码的前缀.1.各种编码方式（2）变长编码这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图ABCD01101111ACB0111D11.各种编码方式从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。1.各种编码方式（3）哈夫曼编码假设编码过程中有以下对应关系：字符ABCD权重（字符出现次数）w1w2w3w4编码长度

8、L1L2L3L4那么总的编码长度为：WPL=w1*L1+w2*L2+w3*L3+w4*L4那么如何选择L1、L2、L3、L4的值，使得WPL最小呢？1.各种编码方式（3）哈夫曼编码可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。