在一棵二叉树中，定义从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径。
从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度
从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。
如果二叉树中的叶结点都带有权值，我们可以把这个定义加以推广。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为该二叉树的带权路径长度（WPL），即：
WPL =
wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。
具有相同叶结点和不同带权路径长度的二叉树
（a）WPL = 1×2+3×2+5×2+7×2 = 32
（b）WPL = 1×2+3×3+5×3+7×1 = 33
（c）WPL = 7×3+5×3+3×2+1×1 = 43
（d）WPL = 1×3+3×3+5×2+7×1 = 29
根据哈夫曼树的定义，要使一棵二叉树的带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼提出的构造哈夫曼树构造算法为：
（1）由给定的n个权值{w1,w2,…,wn}构造n棵只有根 结点的二叉树，从而得到一个二叉树森林F={T1,T2,…,Tn}。
（2）在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和。
（3）在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。
（4）重复步骤（2）和（3），当二叉树森林F中只剩下一棵二叉树时，这棵二叉树就是所构造的哈夫曼树。
对于一组给定的叶结点，设它们的权值集合为{7,5,3,1}，按哈夫曼树构造算法对此集合构造哈夫曼树的过程如图所示。
哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下：
设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶结点，以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。
哈夫曼编码的数据结构设计
设计哈夫曼树的结点存储结构为双亲孩子存储结构。
存放哈夫曼编码的存储结构为
//哈夫曼树的结点类
public class HaffNode {
int weight; //权值
int parent;//双亲
int flag;//标志
int leftChild; //左孩子
int rightChild;//右孩子
HaffNode() {
}
}//哈夫曼编码类
public class Code {
int[] bit; //编码数组
int start; //编码的开始下标
int weight; //权值
Code(int n) {
bit = new int[n];
start = n - 1;
}
}/哈夫曼树类
public class HaffmanTree {
//最大权值
static final int MAXVALUE = 1000;
int nodeNum; //叶子结点个数
public HaffmanTree(int n) {
this.nodeNum = n;
}
//构造哈夫曼树算法
public void haffman(int[] weight, HaffNode[] nodes) {
int n = this.nodeNum;
//m1,m2,表示最小的两个权值，x1,x2,表示最小两个权值对应的编号
int m1, m2, x1, x2;
//初始化所有的结点，对应有n个叶子结点的哈夫曼树，有2n-1个结点。
for (int i = 0; i < 2 * n - 1; i++) {
HaffNode temp = new HaffNode();
//初始化n个叶子结点
if (i < n) {
temp.weight = weight[i];
} else {
temp.weight = 0;
}
temp.parent = 0;
temp.flag = 0;
temp.leftChild = -1;
temp.rightChild = -1;
nodes[i] = temp;
}
//初始化n-1个非叶子结点
for (int i = 0; i < n - 1; i++) {
m1 = m2 = MAXVALUE;
x1 = x2 = 0;
for (int j = 0; j < n + i; j++) {
if (nodes[j].weight < m1 && nodes[j].flag == 0) {
m2 = m1;
x2 = x1;
m1 = nodes[j].weight;
x1 = j;
} else if (nodes[j].weight < m2 && nodes[j].flag == 0) {
m2 = nodes[j].weight;
x2 = j;
}
}
nodes[x1].parent = n + i;
nodes[x2].parent = n + i;
nodes[x1].flag = 1;
nodes[x2].flag = 1;
nodes[n + i].weight = nodes[x1].weight + nodes[x2].weight;
nodes[n + i].leftChild = x1;
nodes[n + i].rightChild = x2;
}
}
//哈弗曼编码算法
public void haffmanCode(HaffNode[] nodes, Code[] haffCode) {
int n = this.nodeNum;
Code code = new Code(n);
int child, parent;
for (int i = 0; i < n; i++) {
code.start = n - 1;
code.weight = nodes[i].weight;
child = i;
parent = nodes[child].parent;
while (parent != 0) {
if (nodes[parent].leftChild == child) {
code.bit[code.start] = 0;
} else {
code.bit[code.start] = 1;
}
code.start--;
child = parent;
parent = nodes[child].parent;
}
Code temp = new Code(n);
for (int j = code.start + 1; j < n; j++) {
temp.bit[j] = code.bit[j];
}
temp.weight = code.weight;
temp.start = code.start;
haffCode[i] = temp;
}
}
}public class Test {
public static void main(String[] args) {
int n = 4;
int[] weight = {1, 3, 5, 7};
HaffmanTree haffTree = new HaffmanTree(n);
HaffNode[] nodes = new HaffNode[2 * n - 1];
Code[] codes = new Code[n];
//构造哈夫曼树
haffTree.haffman(weight, nodes);
//生成哈夫曼编码
haffTree.haffmanCode(nodes, codes);
//打印哈夫曼编码
for (int i = 0; i < n; i++) {
System.out.print("Weight=" + codes[i].weight + " Code=");
for (int j = codes[i].start + 1; j < n; j++) {
System.out.print(codes[i].bit[j]);
}
System.out.println();
}
}
}运行结果：
