参考:http://www.cnblogs.com/wuyuankun/p/3982216.html
http://www.cnblogs.com/yaowen/p/4268157.html
哈夫曼树又称最优二叉树,
是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点
的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度
为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)
,N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径
长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼编码步骤:
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步,直到集合F中只有一棵二叉树为止。简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3,如图:
虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:
再依次建立哈夫曼树,如下图:
其中各个权值替换对应的字符即为下图:
所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010
霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。
//哈夫曼树类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,表示最小两个权值对应的编号,m1表示最小,m2表示次小 int m1,m2,x1,x2; //初始化所有的结点,对应有n个叶子结点的哈夫曼树,有2n-1个结点。 for(int i=0;i < 2*n-1;i++) { HaffNode temp = new HaffNode(); //初始化n个叶子结点,就是输入的节点。0、1、2、3是叶子节点也是输入的节点 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; } for(int i=0;i< n;j++) { temp.bit[j] = code.bit[j]; } temp.weight = code.weight; temp.start = code.start; haffCode[i] = temp; } }}//哈夫曼树的结点类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 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
哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下:
设需要编码的字符集合为{d1,d2,…,dn},各个字符在电文中出现的次数集合为{w1,w2,…,wn},以d1,d2,…,dn作为叶结点,以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。