1 package ren.laughing.datastructure.baseImpl;  2   3 import ren.laughing.datastructure.base.List;  4   5 /**  6  * 创建Huffman树  7  * 生成Huffman编码  8  * @author Laughing_Lz  9  * @time 2016年4月14日 10  */ 11 public class HuffmanTree { 12     /** 13      * 创建Huffman树 14      * @param nodes 15      * @return 16      */ 17     public HuffmanTreeNode buildHuffmanTree(HuffmanTreeNode[] nodes){ 18         int n = nodes.length; 19         if(n < 2){ 20             return nodes[0]; 21         } 22         List list = new ArrayList(); 23         for(int i = 0;i
     
      ((HuffmanTreeNode)list.get(i)).getWeight()){
   //★ 44                 list.insert(i, node); 45                 return; 46             } 47         } 48         list.insert(list.getSize(), node);//若node的weight最小，放在list最后 49         return; 50     } 51     /** 52      * 生成Huffman编码 53      * @param root 54      */ 55     public void generateHuffmanCode(HuffmanTreeNode root){ 56         if(root == null){ 57             return; 58         } 59         if(root.hasParent()){ 60             if(root.isLChild()){ 61                 root.setCoding(root.getParent().getCoding()+"0"); 62             } 63             if(root.isRChild()){ 64                 root.setCoding(root.getParent().getCoding()+"1"); 65             } 66         } 67         generateHuffmanCode(root.getLChild()); 68         generateHuffmanCode(root.getRChild()); 69     } 70     public static void main(String[] args) { 71         HuffmanTreeNode[] nodes = creatHuffmanNodes(); 72         HuffmanTree huffmanTree = new HuffmanTree(); 73         HuffmanTreeNode root = huffmanTree.buildHuffmanTree(nodes); 74         System.out.println("构建的Huffman树根结点是"+root.getData()+",高度为："+root.getHeight()+",权值为："+root.getWeight()); 75         huffmanTree.generateHuffmanCode(root); 76         System.out.println(root.getRChild().getRChild().getLChild().getCoding());//★Huffman编码针对叶子结点，root结点无编码 77     } 78     /** 79      * 创建HuffmanNode结点组合 80      * @return 81      */ 82     public static HuffmanTreeNode[] creatHuffmanNodes(){ 83         HuffmanTreeNode[] nodes = new HuffmanTreeNode[7]; 84         HuffmanTreeNode node1 = new HuffmanTreeNode(1, 'A'); 85         HuffmanTreeNode node2 = new HuffmanTreeNode(2, 'B'); 86         HuffmanTreeNode node3 = new HuffmanTreeNode(3, 'C'); 87         HuffmanTreeNode node4 = new HuffmanTreeNode(4, 'D'); 88         HuffmanTreeNode node5 = new HuffmanTreeNode(5, 'E'); 89         HuffmanTreeNode node6 = new HuffmanTreeNode(6, 'F'); 90         HuffmanTreeNode node7 = new HuffmanTreeNode(7, 'G'); 91         nodes[0] = node2; 92         nodes[1] = node5; 93         nodes[2] = node1; 94         nodes[3] = node3; 95         nodes[4] = node4; 96         nodes[5] = node7; 97         nodes[6] = node6; 98         return nodes; 99     }100 }