霍夫曼树の创建、编码、解码

开头

霍夫曼树的相关概念就不一一赘述了，直接上代码。放心，必要的地方我会加上我自己都看不懂的注释

Mr.Winterの实验要求：

读取一个文本文件，并统计出每个字符的出现次数。随后将一个字符的出现次数作为字符的权值（霍夫曼树中的叶子节点的权值）
将字符和其权值保存起来（链表？or动态数组？）
利用得到的所有字符，构建霍夫曼树（拿到霍夫曼树的根节点）
对每一个字符进行霍夫曼编码，并得到一张编码表
根据编码表，输入一个编码后能够对其进行解码并返回其所对应的字符

步骤

读取文本文件并统计各个字符的出现次数（权值）

package readtxt;

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class ReadTxt {

    /**
     * 传入txt路径读取txt文件
     *
     * @param txtPath
     * @return 返回读取到的内容
     */
    public static HashMap<String, Integer> readTxtAndCount(String txtPath) throws IOException {
        File file = new File(txtPath);
        FileInputStream fileInputStream = new FileInputStream(file);
        InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream);
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);

        StringBuffer sb = new StringBuffer();
        String text = null;
        while ((text = bufferedReader.readLine()) != null) {//按行读取字符串
            sb.append(text);//将每一行保存到StringBuffer缓冲里
        }
        String txt = sb.toString();//保存为字符串
        char[] TXT = txt.toCharArray();//将字符串保存为字符数组
        Map<String, Integer> m = new HashMap<String, Integer>();//创建哈希表（类似键值对），统计字符出现的次数
        for (char c : TXT) {
            String s = String.valueOf(c);//取出一个字符
            if (null != m.get(s)) {//若该字符不是第一次出现
                int count = m.get(s);//取出之前出现的次数count
                m.put(s, count + 1);//+1
            } else {
                m.put(s, 1);//若一次也没有出现，则置为1
            }
        }
        return (HashMap<String, Integer>) m;
    }

    public static void main(String[] args) throws IOException {
        HashMap<String,Integer> m=ReadTxt.readTxtAndCount("U:\\烂盘\\dark二\\带二第二学期\\程序设计综合实验\\实验3\\Demo.txt");
    }
}

值得一提的是，哈希表yyds。它的作用类似Python里面的字典（键值对），字符:出现次数

创建节点类Node保存字符信息

package node;

public class Node implements Comparable<Node> {
    //字符
    public String sign;
    //每个叶子节点对应的哈夫曼编码
    String code;
    //叶子节点的权重
    public int weight;
    //非叶子节点的左右孩子
    public Node lchild;
    public Node rchild;
    Node next;//叶子节点的enxt，用于专门指向root，便于后续的解码操作

    public Node(String sign, int weight) {
        this.sign = sign;
        this.weight = weight;
    }

    public String getCode() {
        return code;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "sign='" + sign + '\'' +
                ", weight=" + weight +
                '}';
    }

    public void CodingByPreOrder(String code, Node root) {//先序遍历哈夫曼树
        if (!this.sign.equals("非叶子节点") && !this.sign.equals("根节点")) {
            this.code = code;
            System.out.println(this.sign + "的哈夫曼编码" + code);
        }
        if (this.lchild != null) {
            this.lchild.CodingByPreOrder(code += "0", root);

        }
        //StringBuilder能够替换原字符串的最后一个字符（仅仅是替换最后一个），不使用String的substring方法是因为这个方法会替换所有与替换字符相同的字符
        StringBuilder sb = new StringBuilder(code);//回溯时，需要修改最后一个字符，将其置为空，下一次向右递归code的最后一个字符就会被置为1
        //replace(参数1，参数2，参数3)，参数1为要替换的开始位置，参数2为要替换的结束位置，参数3为替换内容,
        code = sb.replace(code.length() - 1, code.length(), "").toString();
        if (this.rchild != null) {
            this.rchild.CodingByPreOrder(code + "1", root);
        }
        //将所有叶子节点的next都指向root节点，方便后续的解码操作
        if (!this.sign.equals("非叶子节点") && !this.sign.equals("根节点")) {
            this.next = root;
        }
    }

    /***
     *
     * @param root 霍夫曼树根节点
     * @param code 输入的一个编码
     * @param index code的索引下标
     * @return
     */
    public String Decoding(Node root, String code, int index) {
        Node ROOT=root;
        StringBuilder s = new StringBuilder();
        while (index < code.length()) {//遍历code的每一个字符（也就是那一串01...）
            if (code.charAt(index) == '0') {
                ROOT = ROOT.lchild;//向左子树移动
            }
            if (code.charAt(index) == '1') {
                ROOT = ROOT.rchild;//向右子树移动
            }
            if (ROOT.next == root) {//如果到达叶子节点，也就是它的next指向了根节点
                s.append(ROOT.sign);
                ROOT=root;//当解码出一个字符，需要将ROOT重置为root根节点，方便进行下一个字符的解码
            }
            index++;//索引后移
        }
        if(ROOT==root){//编码全部正确
            System.out.println(code+ "解码后对应的字符为" + s.toString());
            return s.toString();
        }
        else if(!s.toString().equals("")&&ROOT.next==null){//部分编码正确的情况
            System.out.println("输入的编码部分有误，仅能解码出部分字符"+s.toString()+"...");
            return s.toString();
        }
        else {//编码全部错误
            System.out.println("输入的编码完全错误，无法解码...");
            return null;
        }
    }
}

利用得到的节点类构建霍夫曼树

package huffmantree;
import node.Node;
import java.util.*;

public class HuffmanTree {
    /*
    public static void main(String[] args) throws IOException {
        Node root = createHuffmanTree(ReadTxt.readTxtAndCount("E:\\烂盘\\dark二\\带二第二学期\\程序设计综合实验\\实验3\\Demo.txt"));
        root.sign = "根节点";
        preOrder(root);
    }*/

    //构建哈弗曼树
    public static Node createHuffmanTree(HashMap<String, Integer> arr) {
        //int count = 0;
        List<Node> nodes = new ArrayList<Node>();
        //将字符出现的次数作为权值value，并以此加入node节点中
        for (String key : arr.keySet()) {
            nodes.add(new Node(key, arr.get(key)));
        }
        //System.out.println(nodes);//打印所有节点（验证）
        Collections.sort(nodes);//将节点排序
        System.out.println("各个字符对应的权重：");
        System.out.println("nodes =" + nodes);
        while (nodes.size() > 1) {
            //取出根节点权值最小的兩顆二叉树
            //取出权值最小的结点（二叉树）
            Node leftNode = nodes.get(0);
            //取出权值第二小的结点（二叉树）
            Node rightNode = nodes.get(1);
            //构建一棵新的二叉树
            Node parent = new Node("非叶子节点", leftNode.weight + rightNode.weight);
            parent.lchild = leftNode;
            parent.rchild = rightNode;
            //删除处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //将parent加入到nodes
            nodes.add(parent);
            //重新排序
            Collections.sort(nodes);
            //System.out.println("第" + (++count) + "次处理后" + nodes);
        }
        return nodes.get(0);
    }

    public static void preOrder(Node root) {//利用先序遍历打印霍夫曼编码表
        if (root != null) {
            root.CodingByPreOrder("", root);
        } else {
            System.out.println("空树无法遍历...");
        }
    }

    public static String deCoding(Node root, String code, int index) {//解码
        return root.Decoding(root, code, index);
    }
}

PS：另外，编码和解码的核心代码在Node类中

主程序的测试代码

import java.io.IOException;
import java.util.Scanner;
import huffmantree.HuffmanTree;
import node.Node;
import readtxt.ReadTxt;

public class Test {
    public static void main(String[] args) throws IOException {
        boolean flag=true;
        Scanner sc=new Scanner(System.in);
        int key=0;
        Node root=new Node(null,0);
        while(flag){
            menu();
            while(true) {
                key = sc.nextInt();
                if(key<1||key>3){
                    System.out.println("请输入正确的序号...");
                    menu();
                }else{
                    break;
                }
            }

            switch (key){
                case 1:
                    root=HuffmanTree.createHuffmanTree(ReadTxt.readTxtAndCount("U:\\烂盘\\dark二\\带二第二学期\\程序设计综合实验\\实验3\\Demo.txt"));
                    HuffmanTree.preOrder(root);
                    break;
                case 2:
                    System.out.println("请输入一个来自编码表的编码...");
                    String s=sc.next();
                    HuffmanTree.deCoding(root,s,0);
                    break;
                case 3:
                    flag=false;
                    break;
            }
        }
    }
    public static void menu() {
        System.out.println("\n    §※§※§※§※§※§ 霍夫曼编码与解码.§※§※§※§※§※§\t\n");
        System.out.println("\t※◎※◎※◎※◎  1. 霍夫曼の编码(获得编码表).※◎※◎※◎※◎\t");
        System.out.println("\t※◎※◎※◎※◎  2. 霍夫曼の解码.※◎※◎※◎※◎\t");
        System.out.println("\t※◎※◎※◎※◎  3. 退出程序.※◎※◎※◎※◎\t");
        System.out.println("\n\t请选择：\t");
    }
}

结果截图：