当前位置：文档之家 › 哈夫曼树及其应用(完美版)

哈夫曼树及其应用(完美版)

  • 格式：pdf
  • 大小：317.11 KB
  • 文档页数：17

下载文档原格式

  / 17

合集下载

编程教学-哈夫曼树及其应用

编程教学-哈夫曼树及其应用

4
A 2
C
2
1
1
B
D
下面对哈夫曼树进行编码，每一个结点的左分支上 面标1，右分支上面标0。
0
7
1
3
04
A
2
2
C
1
1
B
D
下面对哈夫曼树进行编码，每一个结点的左分支上 面标1，右分支上面标0。
0
7
1
3
04
1
A
2
2
C
1
1
B
D
下面对哈夫曼树进行编码，每一个结点的左分支上 面标1，右分支上面标0。
0
7
1
4
2
2
3
C
A
1
1
B
D
对于字符串“ABACCDA”，共有7个字符，4种字符。 其中A、B、C、D出现的次数分别为3、1、2、1。根 据权值{3，1，2，1} 构造哈夫曼树
3
4
A 2
C
2
1
1
B
D
对于字符串“ABACCDA”，共有7个字符，4种字符。 其中A、B、C、D出现的次数分别为3、1、2、1。根 据权值{3，1，2，1} 构造哈夫曼树
从根结点到各个叶子结点，所经分支上面的0、1 序列，就是该叶子结点所代表字符的编码。
0
7
1
3
04
1
A 2
C
2
0
1
1
1
B
D
A：0 B：110 C：10 D：11
从根结点到各个叶子结点，所经分支上面的0、1 序列，就是该叶子结点所代表字符的编码。
0
7
1
3
04

哈夫曼编码树实现及应用场景讲解

哈夫曼编码树实现及应用场景讲解

哈夫曼编码树实现及应用场景讲解哈夫曼编码树（Huffman coding tree）是一种被广泛应用于数据压缩的算法，它通过利用输出频率不同的字符分配不同长度的编码，从而实现数据的高效压缩。

本文将介绍哈夫曼编码树的实现方法，并探讨其在实际应用中的场景。

一、哈夫曼编码树的实现方法1.1 字符频率统计在构建哈夫曼编码树之前，我们首先需要对目标数据中的字符进行频率统计。

可以通过遍历数据集，并利用哈希表或数组记录每个字符出现的次数。

例如，对于字符串"Hello World!"，我们可以统计出每个字符的频率为：H: 1, e: 1, l: 3, o: 2, W: 1, r: 1, d: 1, !: 1。

1.2 构建哈夫曼编码树构建哈夫曼编码树的过程分为两个步骤：创建叶节点集合和合并节点。

创建叶节点集合：根据字符频率统计结果，创建一个包含所有字符的叶节点集合。

每个叶节点包含字符、频率以及指向其左右子节点的指针（若存在子节点）。

合并节点：从叶节点集合中选取频率最低的两个节点，合并成一个新节点，该新节点的频率等于这两个节点的频率之和。

将合并后的节点插入叶节点集合中，并从集合中移除被合并的节点。

重复该操作，直到叶节点集合只剩下一个节点，即为哈夫曼编码树的根节点。

1.3 构建哈夫曼编码表遍历哈夫曼编码树，沿着根节点到叶节点的路径，给每个字符赋予对应的二进制编码。

例如，对于字符串"Hello World!"，哈夫曼编码表如下：H: 00e: 01l: 10o: 11W: 010r: 011d: 100!: 101二、哈夫曼编码树的应用场景2.1 数据压缩哈夫曼编码树最常见的应用场景之一是数据压缩。

通过使用较短的二进制编码表示频率较高的字符，以及使用较长的二进制编码表示频率较低的字符，可以大幅减小数据的存储空间。

这种压缩方法被广泛应用于文本、图像和音频等多媒体数据的传输和存储。

举个例子，在一个文件中，字符'E'出现频率最高，通过哈夫曼编码树，我们可以将其编码为一个比特（如0），而字符'Z'出现频率最低，可以将其编码为多个比特（如11001），从而实现数据的高效压缩。

哈夫曼树

哈夫曼树

哈夫曼树及其应用一、基本术语1．路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。

通路中分支的数目称为路径长度。

若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2．结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3．树的带权路径长度树的带权路径长度(Weighted Path Length of Tree)：也称为树的代价，定义为树中所有叶结点的带权路径长度之和，通常记为：其中：n表示叶子结点的数目wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。

二、哈夫曼树构造1．哈夫曼树的定义在权为w l，w2，…，w n的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。

【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。

构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=46(c)WPL=7*1+5*2+2*3+4*3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

2．哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。

n 个权值分别设为w1,w2,…,wn,则哈夫曼树的构造规则为：(1) 将w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。

下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如下图所示。

哈夫曼树及其应用

哈夫曼树及其应用

第三节哈夫曼树及其应用1．哈夫曼树的定义在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。

这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158构造哈夫曼树的过程：（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。

这棵二叉树就是哈夫曼树。

假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。

这就是以上述8个权值为叶子结点权值构成的哈夫曼树，它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2712．判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。

例如，编制一个程序，将百分制转换成五个等级输出。

大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if (socre<60) printf("bad");else if (socre<70) printf("pass");else if (score<80) printf("general");else if (score<90) printf("good");esle printf("very good");在实际应用中，往往各个分数段的分布并不是均匀的。

哈夫曼树的实际应用

哈夫曼树的实际应用

哈夫曼树的实际应用
哈夫曼树（Huffman Tree）是一种重要的数据结构，它在信息编码和压缩、数据传输和存储、图像处理等领域有广泛应用。

1. 数据压缩：哈夫曼树是一种无损压缩的方法，能够有效地减小数据的存储空间。

在进行数据压缩时，可以使用哈夫曼树构建字符编码表，将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示，从而减小数据的存储空间。

2. 文件压缩：在文件压缩领域，哈夫曼树被广泛应用于压缩算法中。

通过构建哈夫曼树，可以根据字符出现的频率来生成不同长度的编码，从而减小文件的大小。

常见的文件压缩格式如ZIP、GZIP等都使用了哈夫曼树。

3. 图像压缩：在图像处理中，哈夫曼树被用于图像压缩算法中。

通过将图像中的像素值映射为不同长度的编码，可以减小图像的存储空间，提高图像传输和存储的效率。

常见的图像压缩格式如JPEG、PNG等都使用了哈夫曼树。

4. 文件传输：在数据传输中，哈夫曼树被用于数据压缩和传输。

通过对数据进行压缩，可以减小数据的传输时间和带宽占用。

在传输过程中，接收方可以通过哈夫曼树解码接收到的数据。

5. 数据加密：在数据加密中，哈夫曼树可以用于生成密钥，从而实现数据的加密和解密。

通过将字符映射为不同长度的编码，可以实
现对数据的加密和解密操作。

哈夫曼树在信息编码和压缩、数据传输和存储、图像处理等领域有广泛应用，能够有效地减小数据的存储空间、提高数据传输效率、实现数据加密等功能。

哈夫曼树

哈夫曼树
32
F
K
11110
111111 110
F 24
0
Z 2
1
K 7
L
U
Z

100
111110
哈夫曼编码的效率。
我们定义该编码方案的平均编码长度为： B(T)=(c1p1+ c2p2 +…+ cnpn)/pt 其中： ci和pi是字符集中第i个字符的代码长度及 其相对频率，pt是字符集的总频率。对本例计算平 均编码长度≈2.565 若采用固定长度编码，每个字母需log28=3位， 而哈夫曼编码只需2.565位，节省空间约12%。 哈夫曼编码对于典型的文本文件将比ASCII编 码节省约40%的空间。
用途：用于通信和数据传送中字符的二进制编码，可以 使文件编码总长度最短。 例字符集： C D E F K L U Z 频 率：32 42 120 24 7 42 37 2
306
0
1 186
C D E
1110 101 0
E 79 0 1 120 0 U D 37 42
1 107 1 65 0 1 L 0 33 42 C 0 1 9
哈夫曼树及其应用
1.问题的提出
在程序设计中，常用一个代码来表示一个 元素，标准ASCII码就是一个例子。它用log2128 即7位提供了128个不同的代码来表示ASCII表中 的128个字符。假设所有代码都等长，则表示n 个不同的代码需要log2n位，称为固定长度编码 （如ASCII码）。如果每个字符的使用频率相等， 则固定长度编码的空间效率最高。但事实上，每 个字符的使用频率并非一样。
if (socre<60) printf(“bad”); else if (socre<70) printf(“pass”); else if (score<80) printf(“general”); else if (score<90) printf(“good”); esle printf(“very good”);

赫夫曼树的作用及应用

赫夫曼树的作用及应用1.引言在计算机科学中，赫夫曼树是一种重要的数据结构，它被广泛应用于数据压缩、存储和解码等领域。

赫夫曼树以其高效的特点，成为了压缩算法中的重要组成部分。

本文将介绍赫夫曼树的作用以及它在不同应用领域中的具体应用。

2.赫夫曼树的基本概念赫夫曼树，也称为最优二叉树，是一种树形结构。

它的构建基于赫夫曼编码算法，该算法通过将频率较高的字符编码为较短的二进制码，从而实现数据的高效压缩。

3.赫夫曼树的构建赫夫曼树的构建过程包括以下几个步骤：1.统计字符频率：遍历待压缩的数据，统计各个字符出现的频率。

2.构建叶子节点：将每个字符及其频率作为叶子节点，构成初始的二叉树。

3.合并节点：选择两个频率最低的节点合并，并将合并后的节点作为新的节点插入二叉树中。

4.重复合并：重复执行合并节点的操作，直到只剩下一个节点，即赫夫曼树的根节点。

4.赫夫曼树的作用赫夫曼树在数据压缩和解压缩中发挥着重要作用，主要体现在以下几个方面：4.1数据压缩赫夫曼树通过赫夫曼编码将频率较高的字符编码为较短的二进制码，从而实现数据的高效压缩。

压缩后的数据体积大大减小，方便存储和传输。

4.2文件压缩赫夫曼树可用于对文件进行压缩，将文件中的字符编码为对应的二进制码，从而减小文件的大小。

在文件传输和存储中，减小文件的大小可以提高传输速度和节省存储空间。

4.3图像压缩赫夫曼树也可用于图像数据的压缩，通过对图像中的像素进行编码，减小图像的大小。

图像压缩在图像处理和存储中起到重要的作用，减小图像的大小可以提高图像的传输速度和存储效率。

4.4视频压缩赫夫曼树在视频编码中也有重要应用，通过对视频帧中的数据进行编码，实现对视频的压缩。

视频压缩可以降低视频的带宽占用率，提高视频传输的效率和稳定性。

5.赫夫曼树的应用举例除了数据压缩方面，赫夫曼树在其他领域也有广泛应用，以下列举几个常见的应用场景：5.1字符串匹配赫夫曼树可以用于字符串匹配算法中，通过构建赫夫曼树和相关数据结构，提高字符串匹配的效率和准确性。

哈夫曼树及其应用


1 0 3 4 B A
1 4 S
C
由Huffman树得Huffman编码为： T B A C S
00 01 10
110 111
出现频率越大的字符，其 Huffman编码越短。
0 3 T 0 6
14 1 0 3 4 B A
1
8
0 2
1 4
S
1 2
C
在一个字符集中，任何一个字符的编码都不是另一个 字符编码的前缀，这种编码称为前缀编码。 我们可以利用二叉树来设计二进制的前缀编码。 约定左分支表示字符‘0’，右分支便是字符‘1’，则可 以用从根结点到叶子结点的路径上的分支字符串作为 该叶子结点字符的编码。如此得到的编码比是前缀编 码。 证明： 假设某一个叶子x结点的编码是另一个叶子结点y 编码的前缀，说明从根结点到叶子结点y中间需经过结 点x，从而说明x有左或右子树，这与x是叶子结点矛盾。 那么现在求最短的二进制编码实际上就是构造哈 夫曼树的过程，由此得到的二进制编码，称哈夫曼编 码。
HuffNode[n+i].weight:= HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild:=x1; HuffNode[n+i].rchild:=x2; end;
end;
const Maxleaf=128; {定义最多叶结点数}
begin
for j:=HuffCode[i].start+1 to n-1 do write(HuffCode[i].bit[j]:10); writeln; end; end;
1. 掌握二叉树的结构特性，了解相应的证明方法。 2. 熟悉二叉树的各种存储结构的特点及适用范围。 3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具 体算法与所采用的存储结构有关。 4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱 或后继之间的直接联系。二叉树的线索化过程是基于对二叉树进

哈夫曼树除哈夫曼编码之外的应用

哈夫曼树除哈夫曼编码之外的应用
除了用于哈夫曼编码外，哈夫曼树还有一些其他的应用，包括：
1. 数据压缩：哈夫曼树被广泛应用于数据压缩算法中，如在文件压缩中常用的Huffman压缩算法。

该算法利用哈夫曼树将
频率较高的字符编码为较短的比特序列，从而实现数据的有效压缩。

2. 图像压缩：哈夫曼树可以用于图像压缩算法中的灰度压缩。

通过统计每个灰度级出现的频率，构建哈夫曼树，并将灰度级映射成相应的哈夫曼编码，实现图像数据的压缩。

3. 加密算法：哈夫曼树可以用于加密算法中，比如基于哈夫曼树的可逆数据隐藏算法。

该算法利用哈夫曼树将目标数据隐藏到另一段数据中，通过哈夫曼编码实现隐藏过程，解密时再利用哈夫曼树将隐藏的数据提取出来。

4. 文件搜索：哈夫曼树可以应用于快速搜索文件数据的场景中。

通过构建文件的哈夫曼树，可以有效地进行关键字搜索，加快搜索速度。

5. 数据库索引：哈夫曼树可以用于数据库的索引结构中，如
B+树索引。

通过利用哈夫曼树的性质，将索引数据进行有序
排列，提高数据库的查询效率。

总之，哈夫曼树的应用非常广泛，不仅限于哈夫曼编码，还可
以应用于数据压缩、图像压缩、加密算法、文件搜索、数据库索引等领域。

哈夫曼树及其应用


53 78
29 29
42
14 15 23 19
7 8 11 8
53
42
58
23 19 29 29
11 8 14 15
53
78
100
42
58
23 19 29 29
11 8 14 15
53 78
▪ 哈夫曼树的应用 ❖ 最佳判定树
学生成绩的分布呈正态分布即：中等成绩的学生较多，而较 好或较差学生均比较少。设其分布规律如下表：
等级 不及格 及格 中等 良好 优秀
分数段 0~59 60~69 70~79 80~89 90~100 比例 5％ 15％ 40％ 30％ 10％
若采用图（a）来进行判断，则80%以上的数据要进行 三次或三次以上的比较才能得到结果。 而如果我们以各分数段人数的占总人数的比例5、15、 40、30、10为权值构造哈夫曼树，可得到（b）所示 的判定树来进行判断可以使大部分数据经过较少次数的 比较得到结果。
n
WPL WK LK k 1
c2 4d
a
b
7
5
WPL=7*3+5*3+2*1+4*2=46
a
bc
d
7
52
4
WPL=7*2+5*2+2*2+4
WPL=7*1+5*2+2*3+4*3=35
▪ 构造Huffman树的方法——Huffman算法
❖ 构造Huffman树步骤
• 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根 结点的二叉树，令起权值为wj
*hc=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char * )malloc(n * sizeof(char)); cd[n-1]＝’\0’； for(i=1;i<=n;i++) { start=n-1;
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
输出根结点和权值
I<2*N? 是
I++
调用 SELECT 函数
计算根结点函数
父结点为两子结点之和
输出两子结点和已构造的结点
是否为根结点？ 是
左子是否为空？
否 此时编码为 0
是
是 右子是否为空 否
编码为 1
结束
（2）设计包含的几个方面： ① 赫夫曼树的建立
赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有 n 棵只含有根结点 的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树， 合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。 显然要进行 n－1 次合并，所以共产生 n－1 个新结点，它们都是具有两个孩子 的分支结点。由此可知，最终求得的赫夫曼树中一共有 2n－1 个结点，其中 n 个结点是初始森林的 n 个孤立结点。并且赫夫曼树中没有度数为 1 的分支结点。 我们可以利用一个大小为 2n--1 的一维数组来存储赫夫曼树中的结点。
（4）重复（2）（3）两步，当 F 中只剩下一棵二叉树时，这棵二叉树便 是所要建立的哈夫曼树。”
二：设计概要
哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树 生成哈夫曼编码后进行译码 。
在数据通信中，经常需要将传送的文字转换成由二进制字符 0、1 组成的二 进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表 0， 右分支代表 1，则从根节点到每个叶子节点所经过的路径分支组成的 0 和 1 的 序列便为该节点对应字符的编码，称之为哈夫曼编码。
③ 字符串的译码 译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到 相等时，即取出其对应的字符存入一个新串中。
三、 详细设计
（1）①赫夫曼树的存储结构描述为：
#define N 50 // 叶子结点数 #define M 2*N-1 // 赫夫曼树中结点总数 typedef struct { int weight; // 叶子结点的权值 int lchild, rchild, parent; // 左右孩子及双亲指针 }HTNode; // 树中结点类型 typedef HTNode HuffmanTree[M+1];
最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高 的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短 传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。
（1）其主要流程图如图所示。
否 否
否
开始 将 data 和权值赋给 ht
结点数是否大于-1 是
for (i=n;i<2*n-1;i++)来自//构造哈夫曼树{
min1=min2=32767;
//int 的范围是-32768—32767
lnode=rnode=-1;
//lnode 和 rnode 记录最小权值的两个结点位置
② 赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需 要定义的类型如下： typedet struct { char ch; // 存放编码的字符 char bits[N＋1]; // 存放编码位串 int len; // 编码的长度 }CodeNode; // 编码结构体类型
数据结构课程设计
设计题目： 哈夫曼树及其应用
学 院：计算机科学与技术 专 业：网 络 工 程 班 级：网 络 131 学 号：1308060312 学生姓名：谢 进 指导教师：叶 洁
2015 年 7 月 12 日
设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称
为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定： 指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径 上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编 码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可 以编译成字符串。
1.以二叉链表存储， 2.建立哈夫曼树； 3.求每个字符的哈夫曼编码并显示。
一：赫夫曼树的构造 “（1）由给定的 n 个权值{W1，W2，…，Wn}构成 n 棵二叉树的集合 F＝{T1，T2，…，Tn},其中每棵二叉树 Ti 中只有一个带权为 Wi 的根节点，其 左右子树均空。 （2）在 F 中选取根结点的权值最小和次小的两棵二叉树作为左、右子树 构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权 值之和； （3）在集合 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉 树加入到集合 F 中；
1、熟悉树的二叉树的存储结构及其特点。
2、掌握建立哈夫曼树和哈夫曼编码的方法。
设计内容： 欲发一封内容为 AABBCAB ……(共长 100 字符,字符包括 A 、B 、C 、D
、E 、F 六种字符)，分别输入六种字符在报文中出现的次数（次数总和为 100）， 对这六种字符进行哈夫曼编码。
设计要求： 对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译 码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称 为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总 希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为 Wi，编码长度为 Li，电文中有 n 种字符，则电文编码总长度为∑WiLi。若将此 对应到二叉树上，Wi 为叶结点的权，Li 为根结点到叶结点的路径长度。那么， ∑WiLi 恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前 缀编码，就是以 n 种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称 为赫夫曼编码。设计实现的功能：
②哈弗曼树的算法
void CreateHT(HTNode ht[],int n)
//调用输入的数组 ht[],和节点数 n
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有结点的相关域置初值-1