哈夫曼树是带权路径长度短的树,权值较大的结点离根较近，使用哈夫曼树可以进行哈夫曼编码,达到压缩数据的作用。今天华清Java学院小编就和大家分享下Java如何构建哈夫曼树。
Java构建哈夫曼树的具体代码：
/**
* 优二叉树(哈夫曼树)
* 根据元素的权值构建哈夫曼树，并设计其哈弗曼编码
* 使用数组存储节点
*/
public class Hufuman {
private int[] weights; //存储权值
private int n;
private TreeNode[] nodes; //存储节点的数组
private int m; //数组长度
class TreeNode{
int weight; //权值
int Parent; //父节点的下标
int lchild; //左孩子下标
int rchild; //右孩子下标
public TreeNode(int weight,int parent,int lchild,int rchild){
this.weight = weight;
this.Parent = parent;
this.lchild = lchild;
this.rchild = rchild;
}}
public Hufuman(){
}
public Hufuman(int[] w){
this.weights = w;
int n = w.length;
if(n <= 1){
throw new IllegalArgumentException();
}
this.n = n;
init();
}
/** 初始化节点数组*/
private void init(){
m = 2*n - 1;
nodes = new TreeNode[m];
int i;
for(i = 0;i < n ;++i){
nodes[i] = new TreeNode(weights[i], -1, -1, -1); //-1表示无父或孩子节点
}
for(;i < m;++i){
nodes[i] = new TreeNode(-1, -1, -1, -1);
}}
/**根据权值构建哈夫曼树*/
public void create(){
int min,secmin;
for(int i = n;i < m;++i){
int[] mins = select(i-1);
min = mins[0];
secmin = mins[1];
nodes[min].Parent = i ;
nodes[secmin].Parent = i;
nodes[i].lchild = min;
nodes[i].rchild = secmin;
nodes[i].weight = nodes[min].weight + nodes[secmin].weight;
}}
/** 从叶子节点逆向求每个字符的哈弗曼编码*/
public String[] hufumanCoding(){
String[] codes = new String[n];
StringBuilder sb ;
for(int i=0;i
sb = new StringBuilder();
for(int c=i,p=nodes[i].Parent;p!=-1;c=p,p=nodes[p].Parent){
if(nodes[p].lchild == c)
sb.append('0'); //左分支表示字符'0'
else
sb.append('1'); //右分支表示字符'1'
}
codes[i] = sb.reverse().toString();
}
return codes;
}
/** 取weight小的两个节点*/
private int[] select(int last){
int min=0; //小值下标
int secmin=0; //次小值下标
int i;
for(i=0;i<=last;++i){
if(nodes[i].Parent==-1){
min = i;
break;
}}
for(i=i+1;i<=last;++i){
if(nodes[i].Parent==-1){
secmin = i;
break;
}}
int temp;
if(nodes[min].weight > nodes[secmin].weight){
temp = min;
min = secmin;
secmin = temp;
}
for(i=i+1;i<=last;++i){
if(nodes[i].Parent!=-1)continue;
if(nodes[i].weight < nodes[min].weight){
secmin = min;
min = i;
}else{
if(nodes[i].weight < nodes[secmin].weight)
secmin = i;
}}
int[] minValues = {min,secmin};
return minValues;
}
public void printTree(){
System.out.println(" | weight | parent | lchild | rchild |");
for(int i=0;i
System.out.print(i+" | "+nodes[i].weight+" | "+nodes[i].Parent+" | "+nodes[i].lchild+" | "+nodes[i].rchild+" |");
System.out.println();
}}
public static void main(String[] args) {
int[] w = {5,29,7,8,14,23,3,11};
Hufuman t = new Hufuman(w);
t.create();
t.printTree();
String[] str = t.hufumanCoding();
for(String s:str){
System.out.println(s);
}}}
