初识哈夫曼树

何为哈夫曼树：

哈夫曼树是压缩算法中非常重要数据结构。百度百科解释：给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

权重的概念：

百度百科：权重是指某一因素或指标相对于某一事物的重要程度，其不同于一般的比重，体现的不仅仅是某一因素或指标所占的百分比，强调的是因素或指标的相对重要程度，倾向于贡献度或重要性。
例如：在一次考试中，60分一下的人数占比为40%,60-70分占比30%，80-90分占比20%，90以上占比10%，如果将需要遍历整个班级成绩，则可以将各个分段的人数占比看做权重。

哈夫曼树的作用：

主要用于文件压缩

哈夫曼压缩原理概述：

在数据存储过程中，一个字符A,在大多数的编码格式中，占一个字节，即8位。如果是字符串数据，例如"hello",就需要很多位的存储单元来进行存储。哈夫曼树压缩的原理就是将文件中使用到的字符单元存储到一颗哈夫曼树种，规定哈夫曼树的左子树用0表示，右子树用1表示，则所有的字符都可以使用多个0、1表示，从而对数据进行压缩和还原，压缩比非常夸张。

哈夫曼树的局限

使用哈夫曼树的过程中，由于每添加一个元素，都需要对整棵树进行重构。所以，对于添加和删除操作的性能消耗大，不适合频繁的插入删除操作。

代码：

节点定义

 public static class Node<T> implements Comparable<Node<T>> {
        T data;
        int weight;
        Node<T> leftChild;
        Node<T> rightChild;
        Node<T> parent;

        public Node(T data, int weight) {
            this.data = data;
            this.weight = weight;
        }

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

构造哈夫曼树：

思路：

1.将所有数据排序
2.从数据集合中移除出最小的两个数据，作为新建节点的左右节点，左右节点的权重之和为新节点的权重。并将该节点添加到数据集合里。
3.循环1、2操作直至集合中只有一个节点
4.将集合中的最后一个节点作为根节点

代码实现：

/**
     * 构造哈夫曼树
     * @param item 新节点的数据域
     * @param data 插入字符串集合
     */
    public HuffmanTree(T item, List<Node<T>> data) {
        List<Node<T>> temp = new ArrayList<>();
        for (Node<T> datum : data) {
            temp.add(datum);
        }
        while (temp.size() >1) {
            Collections.sort(temp);
            Node left = temp.remove(0);
            Node right = temp.remove(0);
            Node<T> parent = new Node<>(item, left.weight + right.weight);
            parent.leftChild = left;
            parent.rightChild = right;
            left.parent = parent;
            right.parent = parent;
            temp.add(parent);
        }
        root = temp.remove(0);
    }

提供遍历方法：

public void traversal(){
        LinkedList<Node<T>> linkedList = new LinkedList();
        linkedList.offer(root);
        while (!linkedList.isEmpty()){
            Node<T> parent = linkedList.pop();
            System.out.println(parent.data);
            if(parent.leftChild!=null) {
                linkedList.offer(parent.leftChild);
            }
            if(parent.rightChild!=null) {
                linkedList.offer(parent.rightChild);
            }
        }
    }

测试和打印

测试代码

 @Test
    public void testHuffman(){
        ArrayList<HuffmanTree.Node<String>> nodes = new ArrayList<>();
        nodes.add(new HuffmanTree.Node("h",5));
        nodes.add(new HuffmanTree.Node("e",4));
        nodes.add(new HuffmanTree.Node("l",10));
        nodes.add(new HuffmanTree.Node("o",6));
        nodes.add(new HuffmanTree.Node("a",20));
        nodes.add(new HuffmanTree.Node("i",9));
        nodes.add(new HuffmanTree.Node("u",78));
        HuffmanTree<String> huffmanTree = new HuffmanTree<>("P",nodes);
        huffmanTree.traversal();
    }

打印结果

P
P
u
a
P
P
P
o
i
P
l
e
h