编程实现WPL

假设有n个权值(w1.w2,,,Wn),试构造一棵有n个叶子结点的二叉树每个叶子结点带权为Wi,则其中WPL最小的二叉称做最优二叉树或赫夫曼树。

赫夫曼树算法

(1)根据给定的n个权值(w1w2…Wn)构成n棵二叉树的集合F(T1T2…Tn其中每棵二叉树Ti中只有一个带权为wi的根结点其左右子树均空。

(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

(4)重复(2)和(3)直到F只含一棵树为止。

这棵树便是赫夫曼树。

如下图

约定左分支表示字符‘0’右分支表示字符‘1’。

则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。

如上图可以得到a、b、c的二级制前缀编码分别为0、10、11。

如何得到使电文总长最短的二级制编码假设每种字符在电文中出现的次数为i,编码长度为j,而电文只有n种字符则电文总长为n种i*j的和。

对应到二叉树上若i表示叶子结点的权值j为从根到叶子的路径长度。

则电文总长恰为二叉树带权路径长度。

所以设计电文总长最短的二级制前缀编码即以N种字符出现的频率作为权值设计一颗赫夫曼树的问题

编程实现赫夫曼树

//将原值存放起来然后先赋予最大值防止s1被重复选择HT[s1].weight

0x3f3f3f3f;for

//0号单元未用所以需要动态分配m1个单元HT[m]表示根结点for

//将1~m号单元中的权重、双亲、左孩子右孩子的下标都初始化为0{HT[i].parent

0;HT[i].lchild

*w;w;}/*――――――――――初始化工作结束下面开始创建赫夫曼树――――――――――*/for

i){

//通过n-1次的选择、删除、合并来创建赫夫曼树Select(HT,

s1,

s2);//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,//

i;HT[s2].parent

i;//这里双亲不为0相当于把s1和s2删除//得到新结点i从森林中删除s1s2将s1和s2的双亲域由0改为iHT[i].lchild

s1;HT[i].rchild

从叶子节点到根节点逆向求赫夫曼树HT中n个叶子节点的赫夫曼编码并保存在HC中

void

(!HC){exit(-1);}//临时空间用来保存每次求得的赫夫曼编码串//对于有n个叶子节点的赫夫曼树各叶子节点的编码长度最长不超过n-1//外加一个\0结束符因此分配的数组长度最长为n即可char*

code

//编码结束符亦是字符数组的结束标志//求每个字符的赫夫曼编码int

i;for

//每次编码的位置初始为编码结束符的位置//从叶子节点遍历赫夫曼树直到根节点while

(father

HT[father].parent;}//为第i个字符的编码串分配存储空间HC[i]

(char*)malloc((n

faild!);exit(-1);}//将编码串从code复制到HCstrcpy(HC[i],

code

从叶子结点开始遍历二叉树直到根结点根结点为HT[2n-1],且HT[2n-1].parent0;

关键步骤是求出各个叶子结点的路径长度用此路径长度*此结点的权值就是

此结点带权路径长度最后将各个叶子结点的带权路径长度加起来即可。

int

0;/*由creat_huffmanTree函数可知HT[1]、HT[2]...HT[n]存放的就是各个叶子结点所以挨个求叶子结点的带权路径长度即可*/for

i){int

0;//置当前路径长度为0//从叶子节点遍历赫夫曼树直到根节点while

(father

//将原值存放起来然后先赋予最大值防止s1被重复选择HT[s1].weight

0x3f3f3f3f;for

//0号单元未用所以需要动态分配m1个单元HT[m]表示根结点for

//将1~m号单元中的权重、双亲、左孩子右孩子的下标都初始化为0{HT[i].parent

0;HT[i].lchild

*w;w;}/*――――――――――初始化工作结束下面开始创建赫夫曼树――――――――――*/for

i){

//通过n-1次的选择、删除、合并来创建赫夫曼树Select(HT,

s1,

s2);//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,//

i;HT[s2].parent

i;//这里双亲不为0相当于把s1和s2删除//得到新结点i从森林中删除s1s2将s1和s2的双亲域由0改为iHT[i].lchild

s1;HT[i].rchild

从叶子节点到根节点逆向求赫夫曼树HT中n个叶子节点的赫夫曼编码并保存在HC中

void

(!HC){exit(-1);}//临时空间用来保存每次求得的赫夫曼编码串//对于有n个叶子节点的赫夫曼树各叶子节点的编码长度最长不超过n-1//外加一个\0结束符因此分配的数组长度最长为n即可char*

code

//编码结束符亦是字符数组的结束标志//求每个字符的赫夫曼编码int

i;for

//每次编码的位置初始为编码结束符的位置//从叶子节点遍历赫夫曼树直到根节点while

(father

HT[father].parent;}//为第i个字符的编码串分配存储空间HC[i]

(char*)malloc((n

faild!);exit(-1);}//将编码串从code复制到HCstrcpy(HC[i],

code

从叶子结点开始遍历二叉树直到根结点根结点为HT[2n-1],且HT[2n-1].parent0;

关键步骤是求出各个叶子结点的路径长度用此路径长度*此结点的权值就是

此结点带权路径长度最后将各个叶子结点的带权路径长度加起来即可。

int

0;/*由creat_huffmanTree函数可知HT[1]、HT[2]...HT[n]存放的就是各个叶子结点所以挨个求叶子结点的带权路径长度即可*/for

i){int

0;//置当前路径长度为0//从叶子节点遍历赫夫曼树直到根节点while

(father

n;printf(请输入叶子结点的个数\n);scanf(%d,

n);int

n,w);printf(哈夫曼树建立完毕\n);printf(各字符赫夫曼编码为\n);HuffmanCoding(HT,

HC,

n);printf(带权路径最小为\n);printf(%d,

countWPL1(HT,