哈夫曼树

哈夫曼树(Huffman Tree)描述

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶子节点的权值乘上其到根节点的路径长度(若根节点为0层，叶节点到根节点的路径长度为叶节点的层数)。

在哈夫曼树中，权重越大的节点越接近根节点。

哈夫曼树相关术语

路径： 在一棵树中，从一个节点往下可以到达的孩子节点或者孙子节点之间的通路，称为路径。图1中，从根节点到节点a之间的通路就是一条路径。

路径长度： 在一条路径中，没经过一个节点，路径长度就要加1。例如在一棵树中，规定根节点所在层数为1层，那么从根节点到第i层节点的路径长度为i - 1。图1中从根节点到节点c的路径长度为3。

节点的权： 给每个节点赋予一个新的值，这个值就是节点的权。例如，图1中节点a的权7，节点b的权为5。

节点的带权路径长度： 指的是根节点到该节点之间的路径长度与该节点的权的乘积。例如，图1中节点b的带权路径长度为 2 * 5 = 10

整棵树的带权路径长度为树中所有叶子节点的带权路径长度之和。通常用WPL来表示。例如图1中所示的树的带权路径长度为：

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

哈夫曼树应用

1. 哈夫曼编码： 在数据通信中用来信息加密
2. 哈夫曼译码： 如果数据通过哈夫曼编码加密，那么接收到数据之后，可以通过哈夫曼译码进行解密。
3. 无损压缩： 可以通过哈夫曼编码对数据进行压缩

哈夫曼加密是可逆操作，加密后的密文可以通过解密还原原始数据。

哈夫曼树的构建过程

对于给定的有各自权重的n个节点，构建步骤如下：

1. 在n个带权重的节点中，选择两个权重最小的节点，组成一棵新的二叉树，且新树的根节点权值为最小两个节点权值的和。
2. 从n个带权重节点中删除步骤1中取出的两个节点，并且将新组成的树的根节点加入到n个带权重节点中。以此类推
3. 重复执行步骤1和步骤2。直到构建完成一棵树。

将构建好的哈夫曼树，每个节点的左子树编码为0，右子树编码为1。这样就可以实现哈夫曼编码，以及数据压缩。

如上图3所示。每个字母都会唯一对应一个编码，这样就可以实现加密

a——0

b——010

c——110

d——111

哈夫曼树代码实现

定义哈夫曼树节点结构:

/**
 * 哈夫曼树节点结构
 */
public class HuffmanNode {
    /** 节点数据 */
    private String data;
    /** 节点权重 */
    private int weight;
    /** 左节点 */
    private HuffmanNode left;
    /** 右节点 */
    private HuffmanNode right;
    /** 父节点，遍历会用 */
    private HuffmanNode parent;

    public String getData() {
        return data;
    }
    public void setData(String data) {
        this.data = data;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
    public HuffmanNode getLeft() {
        return left;
    }
    public void setLeft(HuffmanNode left) {
        this.left = left;
    }
    public HuffmanNode getRight() {
        return right;
    }
    public void setRight(HuffmanNode right) {
        this.right = right;
    }
    public HuffmanNode getParent() {
        return parent;
    }
    public void setParent(HuffmanNode parent) {
        this.parent = parent;
    }
    
}

哈夫曼树相关操作类：

import java.util.*;

/**
 * 哈夫曼树
 */
public class HuffmanTree {
    /** 根节点 */
    private HuffmanNode root;
    /** 叶子节点，用于后期权重计算 */
    private List<HuffmanNode> leafNodes;
    /** 每个数据的权重映射表 */
    private Map<Character, Integer> weightMapping;

    public HuffmanTree(Map<Character, Integer> weightMapping) {
        this.weightMapping = weightMapping;
        this.leafNodes = new ArrayList<HuffmanNode>();
    }

    /**
     * 构建哈夫曼树
     */
    public void createHuffmanTree() {
        Character[] keys = weightMapping.keySet().toArray(new Character[0]);
        // 初始化一个优先队列
        PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<HuffmanNode>();
        for (Character character : keys) {
            HuffmanNode node = new HuffmanNode();
            node.setData(character.toString());
            node.setWeight(weightMapping.get(character));
            priorityQueue.add(node);
            this.leafNodes.add(node);
        }
        int len = priorityQueue.size();
        for (int i = 1; i <= len - 1; i++) {
            HuffmanNode nodeLeft = priorityQueue.poll();
            HuffmanNode nodeRight = priorityQueue.poll();

            HuffmanNode newNode = new HuffmanNode();
            newNode.setData(nodeLeft.getData() + nodeRight.getData());
            newNode.setWeight(nodeLeft.getWeight() + nodeRight.getWeight());
            newNode.setLeft(nodeLeft);
            newNode.setRight(nodeRight);
            nodeLeft.setParent(newNode);
            nodeRight.setParent(newNode);

            priorityQueue.add(newNode);
        }
        // 弹出的就是根节点
        this.root = priorityQueue.poll();
    } 

    /**
     * 对叶子节点进行编码操作
     * @return 返回叶子节点编码表
     */
    public Map<Character,String> encoding() {
        Map<Character, String> codMapping = new HashMap<Character,String>();

        for (HuffmanNode huffmanNode : this.leafNodes) {
            if(huffmanNode != null) {
                HuffmanNode currentNode = huffmanNode;
                char cData = huffmanNode.getData().charAt(0);
                String code = "";
                do {
                    // 说明当前节点是左子树节点
                    if (currentNode != null && currentNode.getParent() != null && currentNode == currentNode.getParent().getLeft()) {
                        code = "0" + code;
                    } else {
                        code = "1" + code;
                    }
                    currentNode = currentNode.getParent();
                } while(currentNode.getParent() != null); // 表示循环到根节点，停止循环
                codMapping.put(cData, code);
            }
        }
        return codMapping;
    }
}

测试运行主类：

import java.util.HashMap;
import java.util.Map;

public class HuffmanTest {

    public static void main(String[] args) {
        Map<Character,Integer> weights = new HashMap<Character,Integer>();
        weights.put('a', 3);
        weights.put('b', 24);
        weights.put('c', 6);
        weights.put('d', 20);
        weights.put('e', 34);
        weights.put('f', 4);
        weights.put('g', 12);
        HuffmanTree huffmanTree = new HuffmanTree(weights);
        // 构建哈夫曼树
        huffmanTree.createHuffmanTree();
        // 对哈夫曼树节点进行编码
        Map<Character,String> code = huffmanTree.encoding();
        System.out.println(code);
    }
}