Java: Huffman Tree与哈夫曼编码

目录

Java: Huffman Tree与哈夫曼编码

一.什么是哈夫曼树？

二.什么是哈夫曼编码？

三.Java实现

1.创建Node节点类

2.构建Huffman Tree

3.设置Huffman编码

4.打印节点信息

5.测试

---

一.什么是哈夫曼树？

        哈夫曼树即最优二叉树(Weighted Path Length of Tree, WPL)，可以实现叶子节点的带权路径最短。

        树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。

        

二.什么是哈夫曼编码？

三.Java实现

1.创建Node节点类

public class Node implements Comparable{
    private Object data;    //数据
    private int weight;     //权值
    public String code = "";    //Huffman编码
    private Node left;      //左子树
    private Node right;     //右子树
    private Node parent;    //双亲节点
    public Node(){}
    public Node(Object data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    public void setCode(String code) {
        this.code = code;
    }

    public void setLeft(Node left) {
        this.left = left;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    public void setParent(Node parent) {
        this.parent = parent;
    }
    public String getCode() {
        return this.code;
    }
    public Node getLeft() {
        return this.left;
    }
    public Node getRight() {
        return this.right;
    }
    public Node getParent() {
        return this.parent;
    }
    public Object getData() {
        return this.data;
    }
    public int getWeight() {
        return this.weight;
    }


    @Override
    //升序
    public int compareTo(Node o) {
//        return Integer.compare(this.weight, o.weight);
        return (this.weight < o.weight) ? -1 : ((this.weight == o.weight) ? 0 : 1);
    }
}

        这里通过实现Comparable接口的compareTo(Object o)方法，方便后续对队列中存储的叶子节点进行排序---Collection.sort()方法。

        然后实现HuffmanCode类，其中包含了构造哈弗曼树方法（buildTree）、设置编码方法（setCode)、打印节点信息方法(preTraversalLeaves)：

2.构建Huffman Tree

        nodeList里面保存了待构建的节点们，因为在Node类里面已经实现了compareTo(Object o)方法，在这里我们使用Collection.sort()方法对Node们按照权重wight大小进行升序排序，权重最小的两个节点被作为左右节点构成一个新节点然后删除那两个最小的节点，新节点的权重为两左右节点权重之和，重复此过程直至队列里面没有Node。

//构建Huffman Tree
    public static Node buildTree(linkedList nodeList) {
        Node root = null;
        Node left = null;
        Node right = null;
        while (nodeList.size() > 1) {
            Collections.sort(nodeList);
            left = nodeList.remove();
            right = nodeList.remove();
            root = new Node(left.getData().toString() + right.getData().toString(), left.getWeight() + right.getWeight());
            root.setLeft(left);
            root.setRight(right);
            nodeList.add(root);
        }
        return root;
    }

这里此代码1：

left = nodeList.remove();

也可以写成2：

left = nodeList.get(nodeList.size()-1);
nodeList.remove(0);

 上1的用法为remove()：检索并删除此列表的头（第一个元素），并返回删除元素；

 上2的用法为remove(index): 删除队列里下标为index的元素；

3.设置Huffman编码

        这里采用了递归的方法实现遍历，并设置哈夫曼编码，向左子树走编码加“0”，向右子树走编码加“1”：

//设置编码
    public static void setCode(Node root) {
        if (root != null) {
            if (root.getLeft() != null) {
                root.getLeft().code = root.getCode() + "0";
                setCode(root.getLeft());
            }
            if (root.getRight() != null) {
                root.getRight().code = root.getCode() + "1";
                setCode(root.getRight());
            }
        }
    }

4.打印节点信息

        这里采用了非递归的遍历方法，笔者主要是为了顺便熟悉下非递归遍历的写法，遍历节点时，既没有左子树也没有右子树的节点即为叶子节点：        

public static void preTraversalLeaves(Node root) {
        if (root != null) {
            Stack stack = new Stack<>();
            while (!stack.empty() || root != null) {
                while (root != null) {
                    //打印叶子节点的信息：data，weight，code
                    if (root.getLeft() == null && root.getLeft() == null) {
                        System.out.println(root.getData().toString() + "  " + root.getWeight() + "  " + root.getCode());
                    }
                    stack.push(root);
                    root = root.getLeft();
                }
                    root = stack.pop();
                    root = root.getRight();
            }
        } else {
            return;
        }
    }

5.测试

public static void main(String[] args) {
        //字符串
        String str = new String("chamberlainisyourfatherhahahahayourdad");
        System.out.println("字符串： " + str);

        //统计各字符出现次数并存入HashMap
        HashMap charCount = new HashMap();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (charCount.get(c) != null) {
                charCount.put(c, charCount.get(c) +1);
            } else {
                charCount.put(c, 1);
            }
        }

        //构建哈夫曼树
        linkedList nodelist = new linkedList<>();
        for (Character c: charCount.keySet()) {
            Node node = new Node(c, charCount.get(c));
            nodelist.add(node);
        }
        Node root = HuffmanCode.buildTree(nodelist);

        //设置哈夫曼编码
        HuffmanCode.setCode(root);

        //打印节点信息
        System.out.println("Data   Weight   Code");
        HuffmanCode.preTraversalLeaves(root);
    }

测试结果为：

字符串： chamberlainisyourfatherhahahahayourdad
Data   Weight   Code
r  4  000
d  2  0010
e  2  0011
i  2  0100
o  2  0101
u  2  0110
y  2  0111
b  1  10000
c  1  10001
f  1  10010
l  1  10011
m  1  10100
n  1  10101
s  1  10110
t  1  10111
h  6  110
a  8  111

测试结果正确，我们很欣慰！ 

我们最后的目标时通过哈夫曼编码的原理实现对信息的压缩；

谢谢观看啊！