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

/** 例如：new BiTree("ABDEGCFH","DBGEAFHC",0,0,8);
* @param preOrder 先序遍历序列
* @param inOrder  中序遍历序列
* @param preIndex 在preOrder中开始位置
* @param inIndex  在inOrder中开始位置
* @param count 结点数
*/
public BiTree(String preOrder,String inOrder,int preIndex,int inIndex,int count) {
    if(count > 0) {
        //1 通过先序获得根结点
        char r = preOrder.charAt(preIndex);
        //2 中序中，根结点的位置
        int i = 0 ;
        for(; i < count ; i ++) {
            if(r == inOrder.charAt(i + inIndex)) {
                break;
            }
        }
        //3 通过中序，截取左子树和右子树
        root = new BiTreeNode(r);
        root.lchild = new BiTree(preOrder,inOrder,preIndex+1, inIndex, i).root;
        root.rchild = new BiTree(preOrder,inOrder,preIndex+1+i,inIndex + i + 1, count-i-1).root;
    }
}

 算法
 private int index = 0;          
      //用于记录preStr的索引值 public BiTree(String preStr) 
 {  
char c = preStr.charAt(index++);     
 if(c != '#') {         
root = new BiTreeNode(c);        
 root.lchild = new BiTree(preStr).root;        
 root.rchild = new BiTree(preStr).root;     
} 
else {         root = null;   
 }
  }

public BiTreeNode createBiTree(String sqBiTree, int index) {
    BiTreeNode root = null;
    if(index < sqBiTree.length()) {
        root = new BiTreeNode(sqBiTree.charAt(index));
        root.lchild = createBiTree(sqBiTree, 2*index+1);
        root.rchild = createBiTree(sqBiTree, 2*index+2);
    }
    return root;
}

 哈夫曼结点类
 public class HuffmanNode { ​    
 public int weight;// 权值     public int flag;
 // 节点是否加入哈夫曼树的标志     
public HuffmanNode parent,lchild,rchild; 
// 父节点及左右孩子节点 ​    
// 构造一个空节点     public HuffmanNode()
{         this(0);     } ​    
 // 构造一个具有权值的节点    
 public HuffmanNode(int weight)
{        
 this.weight = weight; 
        flag=0;        
 parent=lchild=rchild=null;     
} }

 哈夫曼编码类
 public class HuffmanTree
 {    
 // 求哈夫曼编码的算法，w存放n个字符的权值(均>0)     
public int[][] huffmanCoding(int[] W)
{         int n = W.length; 
 // 字符个数         
int m = 2*n -1;   
//哈夫曼树的节点数         
// 构造n个具有权值的节点         
HuffmanNode[] HN = new HuffmanNode[m];         
int i = 0;        
 for (; i<n ; i++) {             
HN[i] = new HuffmanNode(W[i]); 
        }        
 // 创建哈夫曼树         
for (i = n;  i<m ; i++) {             
// 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2             
HuffmanNode min1 = selectMin(HN,i-1);            
 min1.flag = 1;             
HuffmanNode min2 = selectMin(HN,i-1);             
min2.flag = 1;             
// 构造 min1和min2的父节点，并修改父节点的权值            
 HN[i] = new HuffmanNode();            
 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 = new int[n][n]; // 分配n个字符编码存储空间         
for (int j =0;j<n;j++){             
// 编码的开始位置，初始化为数组的结尾             
int start = n-1;            
 // 从叶子节点到根，逆向求编码           
  for(HuffmanNode c = 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; ​         } ​         
return HuffCode; ​     } ​     // 在HN[0...1]选择不在哈夫曼树中，且权值weight最小的两个节点min1和min2     
private HuffmanNode selectMin(HuffmanNode[] HN, int end) {        
 // 求 不在哈夫曼树中， weight最小值的那个节点         
HuffmanNode min = HN[end];        
 for (int i = 0; i < end; i++) {             
HuffmanNode h = HN[i];             
// 不在哈夫曼树中， weight最小值           
 if(h.flag == 0 && h.weight<min.weight){                
 min = h;             }         }        
 return min;     } ​ ​ }

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