第六章 树和二叉树演示.pptVIP

结束第*页第六章树和二叉树演示第1页，共20页，星期日，2025年，2月5日第六章树和二叉树6.7哈夫曼树及应用6.7.1哈夫曼树及构造6.7.1哈夫曼编码第2页，共20页，星期日，2025年，2月5日6.7哈夫曼树及应用6.7.1哈夫曼树及构造1哈夫曼树的概念路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；路径长度：路径上的分支数目称为路径长度；结点的权：根据应用的需要可以给树的结点赋权值；结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；树的带权路径长度=树中所有叶子结点的带权路径之和；

通常记作WPL=?wi?Li哈夫曼树：假设有n个权值(w1,w2,…,wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。第3页，共20页，星期日，2025年，2月5日6.7哈夫曼树及应用2应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。可用二叉树描述判定过程。参见课本P145图6.23(a)。如果这个程序很不经常使用，或要转换的分数不多，不必考虑该程序效率，我们可以按照这个流程编程。可是如果该程序经常要使用或数据量很大。比如对北京市几十万小学生的分数进行转换，在这种情况下，要考虑转换程序的效率。

设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：

分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.10第4页，共20页，星期日，2025年，2月5日6.7哈夫曼树及应用按图的判定过程，转换一个分数所需的比较次数=从根到对应结点的路径长度。转换10000个分数所需的总比较次数=10000（0.05?1+0.15?2+0.4?3+0.3?4+0.1?4）若将学生成绩在5个等级以上的分布比例看作描述判定过程二叉树叶子结颠点权值，（0.05?1+0.15?2+0.4?3+0.3?4+0.1?4）正是该二叉树的带权路径长度。可见要想获得效率较高的转换程序，可构造以分数的分布比例为权值的哈夫曼树。403060155101530100第5页，共20页，星期日，2025年，2月5日6.7哈夫曼树及应用3哈夫曼树的构造构造哈夫曼树的步骤：1．根据给定的n个权值，构造n棵只有一个根结点的二叉树，n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合2．在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和；3．从F中删除这两颗树，并将新树加入F；4．重复2、3，直到F中只含一颗树为止；第6页，共20页，星期日，2025年，2月5日6.7哈夫曼树及应用403060155101530403060155101530100例：构造以W=（5，15，40，30，10）为权的哈夫曼树。305101540403015510154030301551015第7页，共20页，星期日，2025年，2月5日6.7哈夫曼树及应用6.7.2哈夫曼编码

哈夫曼树除了能求解最优判定问题解，还用于其他一些最优问题的求解。这里介绍用哈夫曼树求解数据的二进制编码。

在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。例如：邮局发电报，发送方将原文转换成二进制字符串，接收方将二进制字符串还原成原文。原文电文（二进制字符串）原文例要传输的原文为ABACCDA

设ABCD的编码为

A；00

B；01

C：10

D：11发送方：将ABACCDA转换成00010010101100接收方：将00010010101100还原为ABACCDA第8页，共20页，星期日，2025年，2月5日6.7哈夫曼树及应用在数据输传时，为省节费用总希望传输的二进制串尽可能短。

可利用二叉树设计不等长编码：例某通讯系统只使用8种字符a、b、c、d、e、f、g