本文共 1118 字，大约阅读时间需要 3 分钟。

算法思路：

1. 以权值分别为W1,W2．．．Ｗｎ的ｎ各结点，构成n棵二叉树T1,T2,．．．Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点；
   (2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi）
   (3) 从F中删除这两棵二叉树，同时将新二叉树加入到F中;
   (4)重复(2)、(3)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman树。

编码原理：

对于给定的字符集D={d1,d2,…,dn}及其频率分布F={w1,w2,…,wn}，用d1,d2,…,dn作为叶结点，w1,w2,…,wn作为结点的权，利用哈夫曼算法构造一棵最优二叉树，将树中每个分支结点的左分支标上"0"；右分支标上"1"，把从根到每个叶子的路径符号(“0"或"1”)连接起来，作为该叶子的编码。

程序实现：

首先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中， 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在父结点左侧，则置码为 0,若在右侧,则置码为 1，最后输出生成的编码。

#include 
   
    #define MAXBIT      100#define MAXVALUE  10000#define MAXLEAF     30#define MAXNODE    MAXLEAF*2 -1typedef struct {    int bit[MAXBIT];    int start;} HCodeType;      typedef struct{    int weight;    int parent;    int lchild;    int rchild;} HNodeType;        //构造一颗哈夫曼树 void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n){ int i, j, m1, m2, x1, x2;    for (i=0; i<2*n-1; i++)   //初始化存放哈夫曼树数组 HuffNode[] 中的结点     {        HuffNode[i].weight = 0;        HuffNode[i].parent =-1;        HuffNode[i].lchild =-1;        HuffNode[i].lchild =-1;    }    for (i=0; i
   

转载地址：http://nrjwi.baihongyu.com/