【数据结构】建立二叉树以及哈夫曼树及哈夫曼编码（二）

publicBiTreeNodecreateBiTree(StringsqBiTree, intindex) {
BiTreeNoderoot=null;
if(index<sqBiTree.length()) {
root=newBiTreeNode(sqBiTree.charAt(index));
root.lchild=createBiTree(sqBiTree, 2*index+1);
root.rchild=createBiTree(sqBiTree, 2*index+2);
    }
returnroot;
}

哈夫曼结点类publicclassHuffmanNode {
​publicintweight;// 权值publicintflag; // 节点是否加入哈夫曼树的标志publicHuffmanNodeparent,lchild,rchild; // 父节点及左右孩子节点​// 构造一个空节点publicHuffmanNode(){
this(0);
    }
​// 构造一个具有权值的节点publicHuffmanNode(intweight){
this.weight=weight;
flag=0;
parent=lchild=rchild=null;
    }
}
哈夫曼编码类publicclassHuffmanTree {
// 求哈夫曼编码的算法，w存放n个字符的权值(均>0)publicint[][] huffmanCoding(int[] W){
intn=W.length;  // 字符个数intm=2*n-1;   //哈夫曼树的节点数// 构造n个具有权值的节点HuffmanNode[] HN=newHuffmanNode[m];
inti=0;
for (; i<n ; i++) {
HN[i] =newHuffmanNode(W[i]);
        }
// 创建哈夫曼树for (i=n;  i<m ; i++) {
// 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2HuffmanNodemin1=selectMin(HN,i-1);
min1.flag=1;
HuffmanNodemin2=selectMin(HN,i-1);
min2.flag=1;
// 构造 min1和min2的父节点，并修改父节点的权值HN[i] =newHuffmanNode();
min1.parent=HN[i];
min2.parent=HN[i];
HN[i].lchild=min1;
HN[i].rchild=min2;
HN[i].weight=min1.weight+min2.weight;
        }
//  从叶子到根 逆向求每个字符的哈夫曼编码int[][] HuffCode=newint[n][n]; // 分配n个字符编码存储空间for (intj=0;j<n;j++){
// 编码的开始位置，初始化为数组的结尾intstart=n-1;
// 从叶子节点到根，逆向求编码for(HuffmanNodec=HN[j],p=c.parent;p!=null;c=p,p=p.parent){
if(p.lchild.equals(c)){
HuffCode[j][start--]=0;
                }else{
HuffCode[j][start--]=1;
                }
            }
// 编码的开始标志为-1，编码是-1之后的01序列HuffCode[j][start] =-1;
​        }
​returnHuffCode;
​    }
​// 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2privateHuffmanNodeselectMin(HuffmanNode[] HN, intend) {
// 求 不在哈夫曼树中， weight最小值的那个节点HuffmanNodemin=HN[end];
for (inti=0; i<end; i++) {
HuffmanNodeh=HN[i];
// 不在哈夫曼树中， weight最小值if(h.flag==0&&h.weight<min.weight){
min=h;
            }
        }
returnmin;
    }
​​}

测试类publicclassDemo02 {
​publicstaticvoidmain(String[] args) {
// 一组权值int[] W= {6,30,8,9,15,24,4,12};
// 创建哈夫曼树HuffmanTreetree=newHuffmanTree();
// 求哈夫曼编码int[][] HN=tree.huffmanCoding(W);
//打印编码System.out.println("哈夫曼编码是： ");
for (inti=0; i<HN.length; i++) {
System.out.print(W[i]+" ");
for (intj=0; j<HN[i].length; j++) {
if(HN[i][j] ==-1){
for (intk=j+1; k<HN[i].length ; k++) {
System.out.print(HN[i][k]);
                    }
break;
                }
            }
System.out.println();
        }
    }
}