数据结构(哈夫曼树，哈夫曼编码)入门篇，JAVA实现

冷不防 2022-11-09 12:46 164阅读 0赞

## 什么是哈夫曼树 ##

哈夫曼树就是一种最优判定树，举个例子，如下一个判断逻辑  
if(s<60) g=1;  
else if(s<70) g=2  
else if(s<80) g=3  
else if(s<90) g=4  
else g=5;  
分数概率图如下  
![在这里插入图片描述][20210315124040920.png_pic_center]

如果按照代码从上到下顺序构造判定树，那么如下图所示，如果有1000个数据需要判定，那么需要比较3150次  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center]

其实我们可以把概率大的区间放在树的高处，概率小的，放在树的低处，如下图的判定数，1000个数据只要比较2700次。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center 1]  
**带权路径长度之和**：根节点到各节点的路径长度与该结点上的权重的乘积  
将上面的成绩区间的概率抽象为叶子节点的权重，比较次数抽象为根到各节点的路径，总比较次数就是带权路径长度之和，很容易看出把权重大的叶节点放在树的高处，权重小的放在低处，这样我们得到的带权路径长度之和就是最小的；  
**而哈夫曼树的定义正是要构造出一颗带权路径长度之和最小的二叉树。**

哈夫曼树的构造可以采取从数组里面取最小值，但是这样做的话，每次插入元素到数组中，因为要维持升序，它会花费很多时间在维护上，时间复杂度为O(N)。于是我们可以采用最小堆，堆的插入操作时间复杂度为O(logN),比起数组还是快很多的。  
哈夫曼树的总体时间复杂度为：创建最小堆(O(N))+插入N-1个数进入堆中(O(NlogN))+从堆中要删除2N-1个结点(O(NlogN))=O(Nlog(N))

## 哈夫曼编码 ##

**等长的编码**  
哈夫曼编码常用于文件压缩。英文ASCALL字符有一百多个，可以用7位来表示这些字符，再加上以为校验码，就是一个字节表示一个字符，i am amy，这段英文需要48位来表示。但是我们发现，只有i,a,y是不同的，加上am，我们只需要2位二进制就能表示一个字符，00–i，01–y，10–am。这样文件大小就被压缩到了6位。但是显然这样的等长的编码压缩是有局限的，一段英文中出现互不相同的字符是有限的，要想获得更好压缩效果，就需要变长的编码  
**变长的编码**  
**让出现频率高的字符的编码短些，让出现频率低的字符的编码长一些**，假设一段文本中，各字符出现频率如下，以及附上它的变长编码,显然如果用等长编码压缩这个文件，那么大小肯定是远超出变长编码

![在这里插入图片描述][2021031515191392.png_pic_center]

变长编码也有一个可以解决的弊端，那就是一个字符的编码不能是另一个编码的前缀，比如把e的编码改为00，那么在解析这串二进制时1011010001，这时解析到0001就会产生二义性，0001代表t，但从左往右解析时，解析到00发现是e，然后01找不到。所以一个编码不能是另一个编码的前缀，这里的e(00)就成为了a,s,t,nl的前缀了，彻底乱套了。  
解决方法就是利用哈夫曼树，**左分支记为0，右分支记为1**，哈夫曼树是二叉树，而我们把叶结点的度改为字符，由于根节点到各个叶子节点的路径是不同的，可以解决前缀问题，再加上，这也符合哈夫曼树的一个特征，尽量把频率高的结点放在树的高处(编码自然也变短了，文件长度也得到压缩)。这简直就是完美匹配啊。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center 2]

## JAVA代码实现 ##

**最小堆(传入类型必须实现了Comparable接口，之后比较大小会调用其compareto方法，并且其比较器的规则是大于返回1，小于返回返回-1。**

//必须传入一个Comparable的实现类，因为后续会用到类的内部比较器
    public class Heap<E extends Comparable> {
        
        Comparable<? super E>[] list;//堆--存储Comparable的实现类
        int size;  //堆长度
        int capacity;//堆容量
    
        public Heap(int capacity){
        
            this.capacity=capacity;
            size=0;
            list=new Comparable[capacity+1];
        }
    
        //初始化，两种方式
        public void Init(E value,int index){
        
            if(index>0)
            {
         list[index]= value;
              size++;
            }
            else
                new RuntimeException("下标越界");
        }
    
        public void Init(E[] list){
        //一般数组下标从0开始，但最小堆里，下标0这个位置不用
            for(int i=0;i<list.length;i++)
                this.list[i+1]=list[i];
            size=list.length;
        }
        
        //创建最小堆
        public  void Build_Min_Heap(){
        
            for(int i=size/2;i>0;i--) {
        //从倒数第二层开始调整最小堆
                int child = 0;
                int parent = i;
                E par_X = (E) list[parent];
                for (; parent * 2 <= size; parent = child) {
        
                    child = parent * 2;
                    if (child + 1 <= size && list[child].compareTo((E) list[child + 1]) == 1)
                        child++;
                    if (par_X.compareTo((E) list[child]) == -1)
                        break;
                    list[parent] = list[child];
                }
            list[parent]=par_X;
            }
        }
    
        //最小堆插入
        public void Min_Insert(E node){
        
            list[++size]=node;
            for(int i=size;i/2>=0;i=i/2){
        
                if(i==1 || list[i/2].compareTo((E)node)==-1){
        
                    list[i]=node;
                    break;
                }
                else{
        
                    list[i]=list[i/2];
                }
            }
        }
    
    
        //最小堆删除
        public E Min_Heap_Delete(){
        
            Comparable DeleteX=list[1];
            Comparable X=list[size--];
            int child=1;
            int parent=1;
            for(;parent*2<=size;parent=child){
        
                child=parent*2;
                if(child+1<=size && list[child].compareTo((E)list[child+1])==1 )
                    child++;
                if(X.compareTo((E)list[child])==1)
                    list[parent]=list[child];
                else
                    break;
            }
            list[parent]=X;
            return (E)DeleteX;
        }

**哈夫曼树实现**

//结点类型
    class TreeNode implements Comparable{
        
        int value;
        String code;
        TreeNode left;
        TreeNode right;
    
        public TreeNode(int value){
        
            this.value=value;
        }
    
        @Override
        public int compareTo(Object o) {
        
            TreeNode tn=(TreeNode) o ;
            if(value>tn.value)
                return 1;
            else if (value<tn.value)
                return -1;
            else return 0;
        }
    }
    
    
    //哈夫曼树
    import java.security.PublicKey;
    
    public class Hfman {
        
        TreeNode root;
    
        //初始化哈夫曼树
        public void Init(TreeNode[] T){
        
            TreeNode r=null;
            Heap<TreeNode> heap = new Heap<TreeNode>(T.length);
            heap.Init(T);
            heap.Build_Min_Heap();
            for(int i=1;i<=T.length-1;i++){
        //合并N-1次
                TreeNode a =heap.Min_Heap_Delete();
                TreeNode b =heap.Min_Heap_Delete();
                r = new TreeNode(a.value+b.value);
                r.left=a;
                r.right=b;
                heap.Min_Insert(r);
            }
            root=heap.Min_Heap_Delete();//堆中仅存最后一个结点就是根节点
        }
    
    
        //哈夫曼编码
       public static String HfmanCode(TreeNode node,String str){
        
            if(node!=null) {
        
                if (node.left != null && node.right != null) {
        
                    HfmanCode(node.left,str+"0");
                    HfmanCode(node.right,str+"1");
                }
                else  //叶子节点
                    node.code=str;
            }
            return "";
       }
    
       //遍历哈夫曼树
        public static void InOder(TreeNode node){
        
            if(node!=null){
        
                InOder(node.left);
                System.out.println(node.value+"："+node.code);
                InOder(node.right);
            }
        }
        
        //测试
        public static void main(String[] args) {
        
            TreeNode[] nodes = new TreeNode[5];
            for(int i=0;i<5;i++)//测试数据1，2，3，4，5
                nodes[i] = new TreeNode(i+1);
            Hfman hfman = new Hfman();
            hfman.Init(nodes);//初始化构建哈夫曼树
            Hfman.HfmanCode(hfman.root,new String());//构造哈夫曼编码
            Hfman.InOder(hfman.root);//先序遍历
    
        }
    
    }

**参考文献（数据结构第二版，陈越编）**

[20210315124040920.png_pic_center]: /images/20221023/5dfe521d875042f59e24e180a1e5264c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/cedcec6a72f844438631f2e4712b3815.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/08fac9c42082484bb248b8b209e9ef78.png
[2021031515191392.png_pic_center]: /images/20221023/9691406dc41c4980af5456a822a1eb13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDY1NTg5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221023/67f25b3947d24a4c9ba417d68c20a773.png