java构建哈夫曼树，实现哈夫曼编码和译码

客官°小女子只卖身不卖艺 2023-03-12 09:15 58阅读 0赞

> 哈夫曼树是一种带权路径长度最短的二叉树，也称为**最优二叉树**。 我们通过一个具体的实例来讲解哈夫曼树的构造以及编码和反编码。  
> 比如说我们要对一字符串进行01编码，该如何做？我们要清楚为什么要使用哈夫曼编码？答案很简单，哈夫曼编码占位可以做到最少。

#### 一、给出指定字符串 ####

![在这里插入图片描述][20200514193357778.png]

#### 二、统计各个字母出现的次数 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70]

#### 三、以每个字母为一个叶子节点，出现次数作为权重，构建哈夫曼树 ####

注：每次挑选两个权重最小的结点执行父节点  
![在这里插入图片描述][20200514194648760.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 1]  
以此类推，得到最终的哈夫曼树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 2]  
我们可以得到根节点的权值为18。

#### 四、进行编码 ####

从根节点开始，路径左为0，右为1（这个不做要求，左1又0也可），从而对用01编码对叶子节点进行编码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 3]  
ajsfhsdhfasdfk jhsd对应的编码就是

> **1000 101 01 110 111 01 00 111 110 1000 01 00 110 1001 101 111 01 00**

#### 五、译码 ####

给定01，译出字符串为多少，比如按照上面的规则对 110111001000 进行译码。  
分析：

> 从第一个进行查找，一个一个比对，第一个数字是1，规则中没有对应的，接着往下11，也没有对应的，再往下110，对应f，接着分析后面的数字（110分离出来，分析剩下的数字），1没有对应的，11没有对应的，111对应h，分离出111，对剩下的数字比对，0没有对应的，00对应d，1没有，10没有，100没有，1000对应a。综上分析110111001000对应的编码为：fhda

到这里我们就分析完毕了，下面看代码演示：

节点类：

public class NodeClass { 
    
        private int num;
        private String ch;
    
        private NodeClass left;
        private NodeClass right;
    
        public NodeClass() { 
        }
    
        public NodeClass( String ch , int num) { 
            this.num = num;
            this.ch = ch;
        }
    
        public int getNum() { 
            return num;
        }
    
        public void setNum(int num) { 
            this.num = num;
        }
    
        public String getCh() { 
            return ch;
        }
    
        public void setCh(String ch) { 
            this.ch = ch;
        }
    
        public NodeClass getLeft() { 
            return left;
        }
    
        public void setLeft(NodeClass left) { 
            this.left = left;
        }
    
        public NodeClass getRight() { 
            return right;
        }
    
        public void setRight(NodeClass right) { 
            this.right = right;
        }
    
        @Override
        public String toString() { 
            return "NodeClass{" +
                    "num=" + num +
                    ", ch='" + ch + '\'' +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

构建哈夫曼树、哈夫曼编码、译码：

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Map;
    
    public class Hafuman { 
    
        public static void main(String[] args) { 
            String str = "ajsfhsdhfasdfkjhsd";
            HashMap<String , Integer> map = new HashMap<String , Integer>();
            for (int i = 0 ; i < str.length(); i++){ 
                String ch = str.charAt(i) + "";
    
                //统计每个字母出现的次数
                if(map.get(ch) == null){ 
                    map.put(ch,1);
                }else { 
                    //为了防止覆盖
                    map.put(ch , map.get(ch) + 1);
                }
            }
            ArrayList<NodeClass> arr = new ArrayList<>();
    
            //map遍历
            for(Map.Entry<String , Integer> en : map.entrySet()){ 
                System.out.println("key:" + en.getKey() + ",value:" + en.getValue() );
                NodeClass no = new NodeClass(en.getKey() , en.getValue());
                arr.add(no);
            }
    
            //构建哈夫曼树
            for(;;){ 
                if(arr.size() > 1){ 
                    NodeClass[] data = getNode(arr);
                    NodeClass root = new NodeClass(null , data[0].getNum() + data[1].getNum());
                    root.setLeft(data[0]);
                    root.setRight(data[1]);
                    arr.add(root);
                }else { 
                    break;
                }
            }
            //TREE就是最终的哈夫曼树
            NodeClass tree = arr.get(0);
            System.out.println(tree);
    
            //key是字符
            Map<String,String> charMaps = new HashMap<>();
            Map<String,String> codeMaps = new HashMap<>();
            allView(tree,"", charMaps, codeMaps);
    
            //编码
            String hafucode = "";
            for(int i = 0; i < str.length(); i++) { 
    
                String ch  = str.charAt(i) + "";
                hafucode += charMaps.get(ch);
            }
            System.out.println( hafucode.length() + "||" + str.length() );
            System.out.println( hafucode );
    
            //反编码
            int index = 0;
            String charStr = "";
            for(int i = 1 ; i <= hafucode.length() ; i++){ 
                String string = hafucode.substring(index , i);
                if(codeMaps.get(string) != null){ 
                    charStr += codeMaps.get(string);
                    index = i;
                }
            }
            System.out.println(charStr);
        }
    
        //取出最小的两个结点
        public static NodeClass[] getNode(ArrayList<NodeClass> arr){ 
            NodeClass[] nos = new NodeClass[2];
            int index1;
            int index2;
            if(arr.get(0).getNum() <= arr.get(1).getNum()){ 
                index1 = 0;
                index2 = 1;
            }else { 
                index1 = 1;
                index2 = 0;
            }
            for(int i = 2 ; i < arr.size() ; i++){ 
                if(arr.get(i).getNum() < arr.get(index1).getNum()){ 
                    index2 = index1;
                    index1 = i;
                    }else if(arr.get(i).getNum() >= arr.get(index1).getNum() && arr.get(i).getNum() < arr.get(index2).getNum()){ 
                    index2 = i;
                }
            }
            nos[0] = arr.get(index1);
            nos[1] = arr.get(index2);
            arr.remove(index1);
            if(index2 > index1){ 
                arr.remove(index2 - 1);
            }else{ 
                arr.remove(index2);
            }
            return nos;
        }
    
    
        public static void allView(NodeClass tree , String code,  Map<String,String> charMaps ,  Map<String,String> codeMaps ){ 
            if(tree.getLeft() == null){ 
                //System.out.println(tree.getCh() + " : " + tree.getNum() + " code:" + code );
                charMaps.put(tree.getCh(), code);//正向编码
                codeMaps.put(code, tree.getCh());//反编码
            }else{ 
                allView(tree.getLeft() , code + "0",charMaps, codeMaps);
                allView(tree.getRight() , code + "1",charMaps, codeMaps);
            }
        }
    }

[20200514193357778.png]: /images/20230312/e071e584fca143a989ef1cbccdc80840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70]: /images/20230312/bf0c4e1c2ade4bc5b41b582892d9fdff.png
[20200514194648760.png]: /images/20230312/d78ba6aa3f5a410c92c5430848f2745b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 1]: /images/20230312/3c075ea4d8c747bcb6b4679e739b436b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 2]: /images/20230312/38ea82b1d72e4e75a4024d13f8c6351d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70 3]: /images/20230312/b1d89c74efd642a09d85fb4941faa14b.png