《哈夫曼树及其应用》PPT课件.ppt

《《哈夫曼树及其应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《哈夫曼树及其应用》PPT课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章（续）哈夫曼树及其应用 设有设有1000010000个学生某门课程的考试成绩的分布如个学生某门课程的考试成绩的分布如下表所示：下表所示：一、问题的提出一、问题的提出分数05960697079 808990100学生比例数0.050.150.400.300.10学生成绩数据分布情况表*问题：现在要编写程序依次根据每个学生的成绩打印出该学生的成绩等级。分数05960697079 808990100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法方法1：a60打印打印bad“yesa70no打印打印passyesa80no打印打印generalyesa90no打印打

2、印goodyes打印打印excellentno5%的学生的学生15%的学生的学生40%的学生的学生30%的学生的学生10%的学生的学生共做31500次比较读取一个学生成绩a循环一万次 i=1i=10000N结束结束 i=i+1分数05960697079 808990100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法方法2：a80打印打印badyesa90noyesnoa70yesnoa60yesno打印打印“good打印打印excellent打印打印pass打印打印general5%的学生的学生15%的学生的学生40%的学生的学生30%的学生的学生10%的学生的

3、学生读取一个学生成绩a循环一万次 i=1i=10000N结束结束分数05960697079 808990100学生比例数0.050.150.400.300.10学生成绩数据分布情况表方法方法2：a80打印打印badyesa90noyesnoa70yesnoa60yesno打印打印“good打印打印excellent打印打印pass打印打印general5%的学生的学生15%的学生的学生40%的学生的学生30%的学生的学生10%的学生的学生共做22000次比较读取一个学生成绩a循环一万次 i=1i=10000N结束结束思考：如何找到一棵最优的判断树使得编写出来的程序的运行时间是最高效的？1.1.

4、哈夫曼树的哈夫曼树的有关概念有关概念 结点的路径长度：结点的路径长度：从根结点沿某条路径到某结点途中所经历的弧的条数从根结点沿某条路径到某结点途中所经历的弧的条数称为该结点的路径长度。称为该结点的路径长度。二、哈夫曼树及其应用二、哈夫曼树及其应用 树的路径长度：树的路径长度：从根结点到每一个叶子结点的路径长度之和。从根结点到每一个叶子结点的路径长度之和。树的带权路径长度树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和称为树的带权树中所有叶子结点的带权路径长度之和称为树的带权路径长度。路径长度。结点的带权路径长度：结点的带权路径长度：某结点的路径长度与该结点上的权值的乘积称为该结某

5、结点的路径长度与该结点上的权值的乘积称为该结点的带权路径长度。点的带权路径长度。1.1.哈夫曼树的哈夫曼树的有关概念有关概念 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：实例：已知某二叉树的四个叶子结点已知某二叉树的四个叶子结点 a,b,c,d分别带权分别带权7，5，2，4，则可构造出有如下几，则可构造出有如下几种不同形式的二叉树：种不同形式的二叉树：aaa777b5b5c2d4c2d4b5c2d 4树的带权路径长度为：WPL=2*7+2*5+2*2+2*4=36树的带权路径长度为：WPL=2*4+3*7+3*5+1*2=46树的带权路径长度为：WPL=1*7+2*5+3*2+3*4=351

6、.1.哈夫曼树的哈夫曼树的有关概念有关概念 二、哈夫曼树及其应用二、哈夫曼树及其应用哈夫曼树的定义：设有n个叶子结点的二叉树，其第i个叶子结点的权值为wi(i=1,2,3,.n),且第i个叶子结点的路径长度为li,则使WPL=wi*li最小的二叉树称为“最优二叉树”或称为“哈夫曼树”。i=1n n2.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用问题：已知n个叶子的权值为w1,w2,.wn，构造一棵最优二叉树。2.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用方法：步骤步骤1:构造一个具有构造一个具有n棵二叉树的森林棵二叉

7、树的森林F=T1,T2,.,Tn，其中，其中Ti是只有一个根结点且根结点的权值为是只有一个根结点且根结点的权值为wi的二叉树。的二叉树。步骤步骤2:在在F中选取两棵其根结点的权值最小的二叉树，从中选取两棵其根结点的权值最小的二叉树，从F中删除这两棵树，并以这两棵二叉树为左右子树构造一棵中删除这两棵树，并以这两棵二叉树为左右子树构造一棵新的二叉树添加到新的二叉树添加到F中，该新的二叉树的根结点的权值为中，该新的二叉树的根结点的权值为其左右孩子二叉树的根结点的权值之和。其左右孩子二叉树的根结点的权值之和。步骤步骤3:判断判断F中是否只有唯一的一棵二叉树。若是，则求中是否只有唯一的一棵二叉树。若是，

8、则求解过程结束；否则，转步骤解过程结束；否则，转步骤2。2.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e15152.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e15152.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有5个叶子结点的权值分别为：

9、5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e1515302.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e151530602.2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用实例：已知有5个叶子结点的权值分别为：5,15,40,30,10；试画出一棵相应的哈夫曼树。a40b30c5d10e151530601003.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应

10、用等长编码：以英文字符编码为例，一般英文字符编码是采用7位二进制数编码（ASCII码）。7位二进制数可以为27个不同的英文字符编码。下面为讨论问题简单起见，假设被编码的字符集中只有4个（即22个）不同字符，故只要两位二进制数即可完成编码。设这4个不同的字符为A，B，C，D，则可进行等长编码如下：3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用等长编码：设这4个不同的字符为A，B，C，D，则可进行等长编码如下：3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用等长编码：设这4个不同的字符为A，B，C，D，则可进行等长编码如下：A:00 B:01 C:10

11、 D:11 则对于电文“ABACCDA”的二进制电码为：总长为14位 译码时，两位一分进行译码，可唯一得到电文：ABACCDA 。3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用压缩编码：即采用不等长的编码方案，将“高频字符”的编码设计得尽可能短一些，把最长的编码留给“低频字符”。例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：A:0 B:00 C:1 D:01问题：译码时可能出现多意性，即译码不唯一：则对于电文“ABACCDA”的二进制电码为：000011010 总长为9位3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用压缩编

12、码：例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：A:0 B:00 C:1 D:01问题：译码时可能出现多意性，即译码不唯一：则对于电文“ABACCDA”的二进制电码为：000011010 总长为9位3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用压缩编码：例如：对于刚才的4个字符的编码问题，可以按如下不等长编码方案进行编码：A:0 B:00 C:1 D:01问题：译码时可能出现多意性，即译码不唯一。则对于电文“ABACCDA”的二进制电码为：000011010 总长为9位 如000011010中的前4个0的译码会有如下几种不同译码：0000AAA

13、A；0000ABA；0000BB思考：如何解决这一问题？问题的关键在于编码是否为无前缀编码。3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用无前缀压缩编码（既哈夫曼编码）：*思想：利用哈夫曼树设计出来的不等长的编码方案一定是无前缀的。*方法：步骤1：将各字符按照其“出现频率”的统计数字安排一个“权值”并作为“叶子”，然后求出相应的哈夫曼树；步骤2：树中各结点到其左孩子的边上的权值设为0、到其右孩子的边上的权值设为1（即所谓左0右1）；步骤3：从根开始到“叶子”所经历的边上的数值的序列即为该“叶子”所对应的字符的编码。三、实例三、实例 已知某通信用电文仅由A、B、C、D这4

14、个字符构成，其出现的频率分别为：8、4、6、2，请给出它们的哈夫曼编码，要求写出相应的哈夫曼树。解：根据哈夫曼算法，求得哈夫曼树如下：208122664BDAC010101 从根开始到叶子得各字符的哈夫曼编码如下：A:0 B:100 C:11 D:101 则对于电文“ABACCDA”的二进制电码为：总长为13位三、实例三、实例补充内容：用一维数组存放单链表静态链表李赵孙周郑吴王钱A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李赵孙周郑吴王钱A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李

15、赵 8 孙周郑吴王钱A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李赵 8 孙周郑吴王钱 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李赵 8 孙 1 周郑吴王钱 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周郑吴王钱 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑吴王钱 3A 0 1 2 3 4 5 6 7 8

16、9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑吴 5 王钱 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王钱 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 9在“孙”的前面插入一个

17、“史”：三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3 史A 0 1 2 3 4 5 6 7 8 9在“孙”的前面插入一个“史”：三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3 史A 0 1 2 3 4 5 6 7 8 9在“孙”的前面

18、插入一个“史”：三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3 史 3A 0 1 2 3 4 5 6 7 8 9在“孙”的前面插入一个“史”：三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3 史 3A 0 1 2 3 4 5 6 7 8

19、9在“孙”的前面插入一个“史”：三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3 史 3A 0 1 2 3 4 5 6 7 8 9在“孙”的前面插入一个“史”：三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4

20、5 6 7 8 9在“孙”的前面插入一个“史”：删除“周”时表的变化：2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孙”的前面插入一个“史”：删除“周”时表的变化：2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1

21、 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孙”的前面插入一个“史”：删除“周”时表的变化：2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A

22、 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孙”的前面插入一个“史”：删除“周”时表的变化：2 李 6 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 92 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8

23、9在“孙”的前面插入一个“史”：删除“周”时表的变化：2 李 6 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9总结：静态链表在插入和删除时一般不需要移动元素，仅需要修改指针即可。但在申请存储空间时需要一次性申请足够大的空间。三、实例三、实例补充内容：用一维数组存放单链表静态链表2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3A 0 1 2 3 4 5 6 7 8 9静态链表的结构类型定义：#defined MAXSIZE 1000 /链表的最大尺寸Typedef struct StaticListNode ElemT

24、ype data;/存放表中元素的值 int next;/指示后继元素的存放位置 StaticListNode,StaticLinkList MAXSIZE;/定义一个数组四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序1.哈夫曼树的结点的物理结构：weightparentlchildrchildTypedef struct HTNode unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/该指针用以申请数组时作为数组名2.结点物理结构的C语言定义：例如：

25、7 7 0 05600 2500 4500 6 634a7b5c2d 4117256111818016 1 2 3 4 5 6 7HT哈夫曼树HT的存储结构如下(HT为HuffmanTree类型)：HT是一个HTNode类型的一维数组，用以存放m个结点元素(m=2n-1,其中n为叶子个数)；即采用静态二叉链表存放哈夫曼树；故HT可以用如下语句为其申请空间：HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);其中 0号单元未用，从HT1开始存放树的结点四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序1.哈夫曼树的结点的物

26、理结构：weightparentlchildrchildtypedef char*HaffmanCode;/HaffmanCode是指向一个 字符型数组的指针类型 3.用n个字符型数组存放n个叶子的哈夫曼编码这n个字符数组的头指针HCi(1in)分别指向一个字符型数组的首地址，又构成一个指针类型的一维数组；“0“1“1“0“0”“1“0“0”.“0“0“1“1“1“0”HC1HC2HCn.则n个字符串数组的头指针HCi(1 in)可以如此定义：HC=(HuffmanCode)malloc(n+1)*sizeof(char*);HCi=(char*)malloc(编码长度+1)*sizeof(c

27、har);四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序4.构造哈夫曼树的程序之实现：算法思想：例如：a7b5c2d 4611187 0 0 05000 2000 4000 0 00000000000 1 2 3 4 5 6 7HT其哈夫曼树HT的存储结构的初始情况如下：针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点)四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序4.构造哈夫曼树的程序之实现

28、：算法思想：例如：a7b5c2d 4611187 0 0 05000 2500 4500 6 03400000000 1 2 3 4 5 6 7HT其哈夫曼树HT的存储结构的初始情况如下：针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点)四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序4.构造哈夫曼树的程序之实现：算法思想：例如：a7b5c2d 4611187 0 0 05600 2500 4500 6 634110250000 1 2

29、3 4 5 6 7HT其哈夫曼树HT的存储结构的初始情况如下：针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点)四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序4.构造哈夫曼树的程序之实现：算法思想：例如：a7b5c2d 4611187 7 0 05600 2500 4500 6 6341172518016 1 2 3 4 5 6 7HT其哈夫曼树HT的存储结构的初始情况如下：针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在

30、1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子应该是i-1个节点中无父亲且权值最小的两个结点)四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序4.构造哈夫曼树的程序之实现：void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)/w是存放是存放n个字符的权值的一维数组，个字符的权值的一维数组，n为叶子个数；构造哈夫曼树为叶子个数；构造哈夫曼树HT;if(n=1)return;m=2*n-1;/n即为叶子数即为叶子数n0,由二叉树性质由二叉树性质3,n0=n2+1,故树中结点数为

31、故树中结点数为2*n-1 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用 for(i=1;i=n;i+)/n个叶子结点赋初值，个叶子结点赋初值，n个叶子最初为个叶子最初为n个根结点个根结点 HTi.weight=wi-1;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;i+)/n-1个度为个度为2的结点赋初值的结点赋初值 HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;i+)/第第i次循环时为第次循环

32、时为第i个结点选择两个儿子结点个结点选择两个儿子结点s1与与s2 Select(HT,i-1,&s1,&s2);/在在i-1棵子树中也即棵子树中也即HT1.i-1中选择无父亲中选择无父亲(parent为为0)/且权值最小的两个结点且权值最小的两个结点(其序号分别为其序号分别为s1和和s2)。该子程序是一个顺序查找过程。该子程序是一个顺序查找过程 HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/建立父子关系建立父子关系 /哈夫曼树哈夫曼树HT构造完毕构造完毕四、

33、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序5.从叶子到根逆向求每个字符的哈夫曼编码的程序之实现：/从叶子到根逆向求每个字符的哈夫曼编码从叶子到根逆向求每个字符的哈夫曼编码;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/申请申请n个字符编码的头指针数个字符编码的头指针数 组的存储空间组的存储空间 cd=(char*)malloc(n*sizeof(char);/申请存放编码的工作数组申请存放编码的工作数组(n+1个字符空间个字符空间)cdn-1=“0”;/当前字符的编码工作数组的最后一个单元存放一个结束符。当前字

34、符的编码工作数组的最后一个单元存放一个结束符。for(i=1;i=n;+i)/第第i次循环时求第次循环时求第i个叶子个叶子(字符字符)的哈夫曼编码的哈夫曼编码 start=n-1;/start指向指向cd数组数组(即工作数组即工作数组)中编码结束符的位置中编码结束符的位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=“0”;/若当前结点是其父亲的左孩子，赋若当前结点是其父亲的左孩子，赋0值值 else cd-start=“1”;/若当前结点是其父亲的右孩子，则

35、赋若当前结点是其父亲的右孩子，则赋1值值 HCi=(char*)malloc(n-start)*sizeof(char);/为存放第为存放第i个字符的编码申请空间个字符的编码申请空间strcpy(HCi,&cdstart);/从从cd复制编码复制编码(串串)到到HC，标准函数，标准函数 strcpy在头文在头文 件中，故程序的最前面应该有伪操作件中，故程序的最前面应该有伪操作#include /i从从1到到n求求n个叶子的编码个叶子的编码 free(cd);/求编码结束，求编码结束，释放工作数组释放工作数组cd所占用的存储空间所占用的存储空间/HuffmanCoding五、小结五、小结:4.哈

36、夫曼树的应用：哈夫曼编码的设计问题。2.哈夫曼树的定义：WPL=wi*li最小的二叉树称为“最优二叉树”或称为“哈夫曼树”。3.哈夫曼树求解的算法思想：3个步骤。1.哈夫曼树的引入：程序优化问题。i=1n n作业:1.假设用于通信的电文仅由6个字母 A,B,C,D,E,F组成,这6个字母在电文中出现的频率高低依次为：3,4,5,8,9,4,试为这6个字母设计哈夫曼编码。2.证明:若哈夫曼树中有n个叶子结点,则该哈夫曼树中共有2n-1个结点。（提示：哈夫曼树中无度数为1的结点,则利用教材第124页二叉树的性质3即可得证）3.试用标准C语言实现根据n个字符（结点）的权值求哈夫曼树及n个字符的哈夫曼编码的子程序，并编制主程序main调用该子程序对其正确性进行验证。End