基本概念：（1）一棵二叉树中定义，从A结点到B结点所经过的分支序列叫A到B的路径，所经过的分支个数叫路径长度；（2）从二叉树的根结点到二叉树中所有叶结点的路径长度之和称为该二叉树的路径长度。
若叶结点带有权值，设二叉树有n个带权值叶结点，定义从根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为该二叉树的带权路径长度（WPL）。那么，对于一组具有确定权值的叶结点，可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树。
根据哈夫曼树定义，要想使二叉树WPL值最小，必须使权值越大的叶结点越靠近根结点，其构造过程如下：
（1）由给定的n个权值{w1，w2,，...,wn}构造n棵只有根结点的二叉树，其实就是n个二叉树散结点互不相连，从而得到一个二叉树森林F。
（2）在二叉树森林F中选根结点权值最小和次小的两棵树作为新的二叉树的左右子树来构造出新的二叉树，新二叉树的根结点权值为左右子树根结点权值之和。
（3）在森林F中删除作为新二叉树左右子树的两棵二叉树，将新的二叉树加入森林F。
（4）重复步骤2和步骤3，当森林F中只剩下一棵二叉树时，即为所构造的哈夫曼树。
如下图：
哈夫曼编码：
哈夫曼树可用于构造代码总长度最短的编码方案。具体为：以需要编码的字符为叶结点，各个字符出现的次数为叶结点权值来构造哈夫曼树，规定哈夫曼树中左分支为0，右分支为1，那么从根结点到每个叶结点所经历的分支对应的0和1组成的序列便为该叶结点（字符）的编码。
哈夫曼树的结点存储结构采用双亲孩子存储结构，仿真指针实现。每个结点包括双亲，左右孩子，权值域和标志域5个域，标志flag为0说明该结点尚未加入到哈夫曼树，为1说明已经加入到哈夫曼树。
weightflagparentleftChildrightChild 至于编码，我们从叶结点到根结点每个路径逐个遍历来得到编码值，所以使用数组来存储编码，又因为是不等长编码，需要一个标志位start表示编码起始位。故我们可以建立一个哈夫曼编码类来封装。
哈夫曼结点类：
package Tree; /** * @author sun * 创建时间：2017年5月3日下午3:23:05 */ //建立基于双亲孩子仿真指针存储结构的哈夫曼结点类 public class HaffNode { int weight;//权值 int flag;//标记 int parent;//双亲结点下标 int leftChild;//左孩子下标 int rightChild;//右孩子下标 public HaffNode(){} } 哈夫曼编码类： package Tree; /** * @author sun * 创建时间：2017年5月3日下午3:25:55 */ //建立保存哈夫曼编码的哈夫曼编码类 public class Code { int[] bit;//编码用数组 int start;//编码的起始下标 int weight;//字符的权值 public Code(int n){ bit = new int[n]; start = n-1; } } 哈夫曼树类： package Tree; /** * @author sun * 创建时间：2017年5月3日下午3:29:33 */ //构造哈夫曼树和哈夫曼编码的哈夫曼树类 public class HaffmanTree { static final int maxValue = 10000;//最大权值 private int nodeNum;//叶子结点个数 public HaffmanTree(int n){ nodeNum = n; } public void haffman(int[] weight,HaffNode[] node){ //构造权值为weight的哈夫曼树 int m1,m2,x1,x2; int n = nodeNum; //哈夫曼树初始化，n个叶结点的哈夫曼树共有2n-1个结点 for(int i=0;i<2*n-1;i++){ HaffNode temp = new HaffNode(); if(i<n) temp.weight = weight[i]; else temp.weight = 0; temp.parent = -1; temp.flag = 0; temp.leftChild = -1; temp.rightChild = -1; node[i] = temp; } //构造哈夫曼树的n-1个非叶结点,取出最小的两棵树合并 for(int i=0;i<n-1;i++){ m1 = m2 = maxValue; x1 = x2 = 0;//x1为最小树，x2为次小树 for(int j=0;j<n+i;j++){ if(node[j].weight<m1 && node[j].flag==0){ m2 = m1; x2 = x1; m1 = node[j].weight; x1 = j; } else if(node[j].weight<m2 && node[j].flag==0){ m2 = node[j].weight; x2 = j; } } //将找出的两棵权值最小的子树合并为一棵子树 node[x1].parent = n+i; node[x2].parent = n+i; node[x1].flag = 1; node[x2].flag = 1; node[n+i].weight = node[x1].weight+node[x2].weight; node[n+i].leftChild = x1; node[n+i].rightChild = x2; } } public void haffmanCode(HaffNode[] node,Code[] haffCode){ //由哈夫曼树构造哈夫曼编码 int n = nodeNum; Code cd = new Code(n); int child,parent; //求n个叶结点的哈夫曼编码 for(int i=0;i<n;i++){ cd.start = n-1;//不等长编码的最后一位为n-1 cd.weight = node[i].weight;//取得编码对应的权值 child = i; parent = node[child].parent; while(parent!=-1){ //由叶结点向上直到根结点循环 if(node[parent].leftChild == child) cd.bit[cd.start] = 0;//左孩子结点编码为0 else cd.bit[cd.start] = 1;//右孩子结点编码1 cd.start--; //System.out.print(cd.start+" "); child = parent; parent = node[child].parent; } Code temp = new Code(n); //保存叶结点的编码和不等长编码的起始位 for(int j=cd.start+1;j<n;j++) temp.bit[j] = cd.bit[j]; temp.start = cd.start; temp.weight = cd.weight; haffCode[i] = temp; } } } 测试： package Tree; /** * @author sun * 创建时间：2017年5月3日下午3:55:33 */ //设有字符集{A,B,C,D},各字符在电文中出现次数集为{1,3,5,7}设计各字符的哈夫曼编码 public class TestHaffman { public static void main(String[] args) { int n = 4; HaffmanTree myHaff = new HaffmanTree(n); int[] weight = {1,3,5,7}; HaffNode[] node = new HaffNode[2*n-1]; Code[] haffCode = new Code[n]; myHaff.haffman(weight, node); myHaff.haffmanCode(node, haffCode); for(int i=0;i<n;i++){ System.out.print("Weight = "+haffCode[i].weight+"Code = "); for(int j=haffCode[i].start+1;j<n;j++){ System.out.print(haffCode[i].bit[j]); } System.out.println(); } } } /* Weight = 1Code = 100 Weight = 3Code = 101 Weight = 5Code = 11 Weight = 7Code = 0 */