(12)哈夫曼树及其应用

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

2、 打印打印general yes a90 no 打印打印good yes 打印打印 excellent no5%的学生的学生 15%的学生的学生 40%的学生的学生 30%的学生的学生 10%的学生的学生 共做31500 次比较 读取一个学生成绩a 循环一万次 i=1 i=10000 N 结束结束 i = i+1 分数05960697079 808990100 学生比例数0.050.150.400.300.10 学生成绩数据分布情况表 方法方法2： a80 打印打印bad yes a90 no yes no a70 yes no a60 yes no 打印打印 “good 打印打印 excel

3、lent 打印打印pass 打印打印general 5%的学生的学生15%的学生的学生 40%的学生的学生 30%的学生的学生 10%的学生的学生 读取一个学生成绩a 循环一万次 i=1 i=10000 N 结束结束 分数05960697079 808990100 学生比例数0.050.150.400.300.10 学生成绩数据分布情况表 方法方法2： a80 打印打印bad yes a90 no yes no a70 yes no a60 yes no 打印打印 “good 打印打印 excellent 打印打印pass 打印打印general 5%的学生的学生15%的学生的学生 40%的学

4、生的学生 30%的学生的学生 10%的学生的学生 共做22000 次比较 读取一个学生成绩a 循环一万次 i=1 i=10000 N 结束结束 思考：如何找到一棵最优的判断树使得编写 出来的程序的运行时间是最高效的？ 1. 1.哈夫曼树的哈夫曼树的有关概念有关概念 结点的路径长度：结点的路径长度： 从根结点沿某条路径到某结点途中所经历的弧的条数从根结点沿某条路径到某结点途中所经历的弧的条数 称为该结点的路径长度。称为该结点的路径长度。 二、哈夫曼树及其应用二、哈夫曼树及其应用 树的路径长度：树的路径长度： 从根结点到每一个叶子结点的路径长度之和。从根结点到每一个叶子结点的路径长度之和。 树的带

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

6、形式的二叉树： a a a 7 7 7 b 5 b 5c 2 d 4 c 2 d 4 b 5 c 2 d 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=35 1. 1.哈夫曼树的哈夫曼树的有关概念有关概念 二、哈夫曼树及其应用二、哈夫曼树及其应用 哈夫曼树的定义： 设有n个叶子结点的二叉树，其第i个 叶子结点的权值为wi(i=1,2,3,.n),且第i个 叶子结点的路径长度为li ,则使 WPL=wi*li最小的二叉树称为“最优 二叉树”或

7、称为“哈夫曼树”。 i=1 n n 2. 2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用 问题： 已知n个叶子的权值为w1,w2,.wn，构 造一棵最优二叉树。 2. 2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用 方法： 步骤步骤1:构造一个具有构造一个具有n棵二叉树的森林棵二叉树的森林F=T1,T2,.,Tn， 其中其中Ti是只有一个根结点且根结点的权值为是只有一个根结点且根结点的权值为wi的二叉树。的二叉树。 步骤步骤2:在在F中选取两棵其根结点的权值最小的二叉树，从中选取两棵其根结点的权值最小的二叉树，从F 中删除

8、这两棵树，并以这两棵二叉树为左右子树构造一棵中删除这两棵树，并以这两棵二叉树为左右子树构造一棵 新的二叉树添加到新的二叉树添加到F中，该新的二叉树的根结点的权值为中，该新的二叉树的根结点的权值为 其左右孩子二叉树的根结点的权值之和。其左右孩子二叉树的根结点的权值之和。 步骤步骤3:判断判断F中是否只有唯一的一棵二叉树。若是，则求中是否只有唯一的一棵二叉树。若是，则求 解过程结束；否则，转步骤解过程结束；否则，转步骤2。 2. 2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用 实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试

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

10、 2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用 实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。 a 40 b 30 c 5 d 10 e 1515 30 60 2. 2.哈夫曼树的哈夫曼树的求解过程求解过程 二、哈夫曼树及其应用二、哈夫曼树及其应用 实例：已知有5个叶子结点的权值分别为：5 , 15 , 40 , 30 , 10 ；试画出一棵相应的哈夫曼树。 a 40 b 30 c 5 d 10 e 1515 30 60 100 3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及

11、其应用 等长编码： 以英文字符编码为例，一般英文字符编码是采 用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，则可进行 等长

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

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

14、唯一。 则对于电文“ABACCDA”的二进制电码为： 000011010 总长为9位 如000011010中的前4个0的译码会有如下几种不 同译码： 0000AAAA；0000ABA；0000BB 思考：如何解 决这一问题？ 问题的关键在于编码 是否为无前缀编码。 3.3.哈夫曼编码哈夫曼编码 二、哈夫曼树及其应用二、哈夫曼树及其应用 无前缀压缩编码（既哈夫曼编码）： *思想：利用哈夫曼树设计出来的不等长的编码方 案一定是无前缀的。 *方法： 步骤1：将各字符按照其“出现频率”的统计数字安排 一个“权值”并作为“叶子”，然后求出相应的哈夫曼树； 步骤2：树中各结点到其左孩子的边上的权值设为0、

15、到 其右孩子的边上的权值设为1（即所谓左0右1）； 步骤3：从根开始到“叶子”所经历的边上的数值的序 列即为该“叶子”所对应的字符的编码。 三、实例三、实例 已知某通信用电文仅由A、B、C、D这4个字符构成， 其出现的频率分别为：8、4、6、2，请给出它们的哈夫 曼编码，要求写出相应的哈夫曼树。 解：根据哈夫曼算法，求得哈夫曼树如下： 20 812 2 66 4 B D A C 0 1 01 01 从根开始到叶子得各字 符的哈夫曼编码如下： A :0 B:100 C:11 D:101 则对于电文“ABACCDA”的二 进制电码为： 0100011111010 总长为13位 三、实例三、实例 补

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

17、 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 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

18、 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 2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 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 2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 3 史A 0 1 2 3

19、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 2 李 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 9 2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0

20、 钱 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 9 2 李 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 9 2 李 4 赵 8

21、 孙 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 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 钱 9 史 3A 0 1 2 3 4 5 6 7 8 9 三、

22、实例三、实例 补充内容：用一维数组存放单链表静态链表 2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 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 钱 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

23、 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 钱 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 2 李 4 赵 8 孙 1 周 6 郑 7 吴 5 王 0 钱 9 史 3A 0 1 2 3 4 5 6 7 8

24、 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 2 李 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 史 3

25、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 9 静态链表的结构类型定义： #defined MAXSIZE 1000 / 链表的最大尺寸 Typedef struct StaticListNode ElemType data ; /存放表中元素的值 int next ; /指示后继元素的存放位置 StaticList

26、Node, StaticLinkList MAXSIZE ; /定义一个数组 四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序 1.哈夫曼树的结点的物理结构： weightparentlchildrchild Typedef struct HTNode unsigned int weight ; unsigned int parent, lchild, rchild ; HTNode , * HuffmanTree ; /该指针用以申请数组时作为数组名 2.结点物理结构的C语言定义： 例如： 7 7 0 05600 2500 4500 6 634 a

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

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

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

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

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

32、5 c 2 d 4 6 11 18 7 7 0 05600 2500 4500 6 634 11 72518016 1 2 3 4 5 6 7 HT 其哈夫曼树HT的存储结构的初始情况如下： 针对第i个结点(n+1i2n-1,n=4为叶子结点的个数)，在 1i-1号结点中为第i个结点寻找两个儿子结点(该两个儿子 应该是i-1个节点中无父亲且权值最小的两个结点) 四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序 4.构造哈夫曼树的程序之实现： void HuffmanCoding(HuffmanTree if (n=1) return; m = 2 *

33、n - 1; /n即为叶子数即为叶子数n0,由二叉树性质由二叉树性质3,n0=n2+1,故树中结点数为故树中结点数为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;

34、 HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) / 第第i次循环时为第次循环时为第i个结点选择两个儿子结点个结点选择两个儿子结点s1与与s2 Select(HT, i-1, / 在在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构造完毕构造完毕 四、构造哈夫曼树并求四、构造哈夫曼树并求n个字符的哈夫曼编码之程序个字符的哈夫曼编码之程序 5.从叶子到根逆向求每个字符的哈夫曼编码的程序之实现： /从叶子到根逆向求每个字符的哈夫曼编码从叶子到根逆向求每个字符的哈夫曼编码; HC=(HuffmanCode)malloc(n+1)*sizeof(cha