赫夫曼（Huffman）树也称最有二叉树，是一类带全路径长度最短的树，有着广泛的应用。比方一棵判定树，依据学生的成绩划分及格还是不及格还是优、中等、良好。显然用if-else或者switch就能够简单实现，当然能够直接毫不考虑的直接这样写，可是假设我们再肯花点功夫，就能够得到更加高效的程序。
我们能够以学生的总的学科分数的占的各个分数段的比率为权，构造一棵赫夫曼树，这样能够降低比較次数，提高程序执行效率。
构造赫夫曼树的方法步骤事实上非常easy--赫夫曼算法：
（1）. 依据给定的n个权值{w1,w2,w3...,wn}构成n棵二叉树的集合F = {T1，T2，....Tn}，当中每棵二叉树Ti中仅仅有一个带权的wi的根节点，其左右子树为空。
（2）. 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和。
（3）. 在F中删除这两棵树，同一时候将新得到的二叉树增加到F中。
（4）. 反复（2）、（3）。知道F中含一棵树为止。
以下是构造HuffmanTree的代码实现：
#include"stdafx.h"
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组，存储哈弗曼树
typedef char** HuffmanCode; //动态分配数组存储哈夫曼编码表
void MaoPao(HuffmanTree HT,int* arr,int number,int &s1,int &s2) //传入HT、数组首地址、数组中元素的个数:m
{
//仅仅需进行两趟比較就可以，得到两个最小数
int i,j,m;
printf("
进入冒泡排序函数...");
for(i = 0;i<2;i++)
{
for(j = 0;j<number - i;j++) //number是数组中的实际元素个数..
{
// printf("
进入循环");
//printf("
arrj = %d,arrj+1 = %d",arr[j],arr[j+1]);
if(HT[ arr[j] ].weight < HT[ arr[j+1] ].weight)
{
m = arr[j];
arr[j] = arr[j+1];
arr[j+1] = m;
}
}
}
s1 = arr[number - 1];
s2 = arr[number];
printf("
.........%d,%d",s1,s2);
}
void Select(HuffmanTree HT,int n,int &s1,int &s2) //n是总的节点数量
{
printf("
进入Select函数");
int arr[20] = {0}; //存放parent为0的节点的编号
int m = 0;
for(int i = 1;i<=n;i++)
{
if(HT[i].parent == 0)
{
arr[m] = i; //从0開始存，那么数组中的元素个数就 = m
m++;
printf("
parent = 0的节点号：%d",i);
if(m > 19)m = 19;
}
}
//比方n = 8,表示一共8个数。最后m++ = 8。实际数组是0~7的。那么m就是数组中的元素个数
//OK,找到parent = 0 的节点，以下选择weight最小的两个。该用什么算法呢？我用的是冒泡法。上浮两个最小数
MaoPao(HT,arr,m,s1,s2); //m是数组中的元素个数..数组从1開始。数组中的最后一个元素是m,倒数一个是m-1得到两个权值最小的节点
}
int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) //n是叶子的数量，w存放n个字符(叶子)的权值
{
int m; //总共的节点数
int s1 = 0;
int s2 = 0; //存储选择到的节点编号
char* cd;
int c;
int f;
int start;
HuffmanTree p;
int i = 0;
if(n <= 1)
return 0;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
for(p = HT+1,i = 1;i <= n; ++i,++p,++w)//第一号单元空出来的。从1開始。这里是初始化操作。分两步。一步是有权值的。已不是没有权值的。用if也是能够的
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(;i <= m;++i,++p)
{
printf("a..aaaaaaa......i = %d",i);
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
printf("初始化完成..");
//建立哈弗曼树
//8，这是后面測试的。
for(i = n+1;i<=m;++i) //这里要循环n-1次，也就是说，构造哈弗曼树须要同一个操作做n-1次,m = 2n-1，2n-1-(n+1)+1 = n-1
{
Select(HT,i-1,s1,s2);
printf("
此时...i = %d,m = %d,,,被选中的编号..%d,%d",i,m,s1,s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
return 1;
}
void ShowHT(HuffmanTree &HT,int n) //n是叶子的数量
{
int m = 2*n - 1; //总共的节点数量
for(int i = 1;i<=m;i++)
{
printf("
编号：%d--Weight:%d Parent: %d LeftChild: %d RightChild；%d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
}
以下是main函数的測试：
#include"stdafx.h"
//#include"BasicGraph2.h"
#include "HuffmanCode.h"
void main()
{
HuffmanTree HT;
HuffmanCode ch;
int n = 8;
int m = 15;
int arr[] = {5,29,7,8,14,23,3,11};
if(HuffmanCoding(HT,ch,arr,n))
ShowHT(HT,n);
}执行结果：
图2：
说明：事实上依据上面的权值，树有多种。可是WPL都是一样的。