数据结构与算法——赫夫曼树（哈夫曼树）

2022-04-13 21:06:10

基本介绍

赫夫曼树（Huffman tree）：

给定 n 个权值作为 n 个 叶子节点，构造一颗二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为 最优二叉树，也称为 哈夫曼树（Huffman Tree），还有的叫 霍夫曼树
赫夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近

详情请看百度百科——哈夫曼树

重要概念

路径和 路径长度：

在一颗树中，从一个节点往下可以到达的孩子或孙子节点之间的通路，称为路径。

通路中分支的数目称为路径长度。若规定根节点的层数为 1，则从根节点到第 L 层节点的路径长度为 L-1
节点的权 和 带权路径长度

若将树中节点赋给一个有着某种含义的数值，则这个数值称为该节点的权。

节点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度

所有叶子节点的带权路径长度之和，记为 WPL（weighted path length），权值越大的节点离根节点越近的二叉树才是最优二叉树
下图WPL 最小的就是赫夫曼树

如上图：

权：元素的值
路径长度：一个节点到另一个节点的一段路，就叫路径长度
带权路径长度：例如从根节点到 13 有3条路径长度，则它的带权路径长度为 13*2=26
树的带权路径长度：如图上的WPL，所有叶子节点的带权路径长度之和

创建思路

以数列 [ 13,7,8,3,29,6,1 ] 进行讲解。

首先将它进行从小到大进行排序，排序后是：1,3,6,7,8,13,29

其中，每一个元素都是一个节点，每个节点可以看成是一颗最简单的二叉树
取出根节点权值最小的两棵树：1 和 3
组成一棵新的二叉树，该二叉树的根节点权值是：这两颗树的权值之和，如下图：
再将这颗新的二叉树，以 根节点的权值大小，再次排序，并不断重复上述步骤

如图所示：将剩余未处理的节点，与新的根节点权值进行排序，那么再次取最小的两棵树 4 和 6，组成新的根节点 10

一般来说，可以将左节点指向权值较大的，右节点指向权值较小的，但是这个不做特别规定。重复以上过程，直到组成如下图这颗赫夫曼树

单单看文字图解，就有点索然无味了，下面进行代码实现。

代码实现

首先进行推导实现，方便理解。

推导实现

/**
 * 赫夫曼树实现
 */
public class HuffmanTreeTest {
    /**
     * 首先推导实现
     */
    @Test
    public void processDemo() {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};

        // 1. 为了实现方便，先将每个元素转成 Node 对象，并装入 arrayList 中
        List<Node> nodes = new ArrayList<>();
        for (int i : arr) {
            nodes.add(new Node(i));
        }

        // 2. 从小到大排序
        Collections.sort(nodes);

        // 3. 取出两个较小的树
        // 因为从小到大排序了
        Node left = nodes.get(0);
        Node right = nodes.get(1);
        // 4. 构成成新的二叉树
        Node parent = new Node(left.value + right.value);
        parent.left = left;
        parent.right = right;
        // 5. 从 list 中删除已经处理过的二叉树
        nodes.remove(left);
        nodes.remove(right);
        // 6. 将新的二叉树添加到 list 中，为下一轮构建做准备
        nodes.add(parent);

        // 最后来看一下结果
        System.out.println("原始数组：" + Arrays.toString(arr));
        System.out.println("新的节点：" + nodes);
    }
}

/**
 * 节点
 *
 * 为了让Node 对象进行排序，用Collections工具类集合排序
 * 让Node 实现Comparable接口，因为会用到 Collections.sort(nodes); 进行排序，所以一定要实现Comparable接口
 */
class Node implements Comparable<Node> {
    int value; // 权
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    /**
     * 为了打印方便
     *
     * @return
     */
    @Override
    public String toString() {
        return value + "";
    }

    /**
     * 从小到大排序
     *
     * @param o
     * @return
     */
    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
}

运行结果输出

原始数组：[13, 7, 8, 3, 29, 6, 1]
新的节点：[6, 7, 8, 13, 29, 4]

可以看到，第一轮的处理之后，的确如我们的创建思路解说一致。

那么创建一颗完整的赫夫曼树的核心代码就在上面，只要对上述步骤进行重复执行，就可以了。

完整实现

   @Test
   public void createHuffmanTreeTest() {
       int[] arr = {13, 7, 8, 3, 29, 6, 1};
       //构建赫夫曼树
       Node huffmanTree = createHuffmanTree(arr);
     
       // 前序遍历
       huffmanTree.list();
   }

   private Node createHuffmanTree(int[] arr) {
       // 1. 为了实现方便，先将每个元素转成 Node 对象，并装入 arrayList 中
       List<Node> nodes = new ArrayList<>();
       for (int i : arr) {
           nodes.add(new Node(i));
       }

       //核心代码重复执行
       while (nodes.size() > 1) {
           // 2. 从小到大排序
           Collections.sort(nodes);

           // 3. 取出两个较小的树
           Node left = nodes.get(0);
           Node right = nodes.get(1);
           // 4. 构成成新的二叉树
           Node parent = new Node(left.value + right.value);
           parent.left = left;
           parent.right = right;
           // 5. 从 list 中删除已经处理过的二叉树
           nodes.remove(left);
           nodes.remove(right);
           // 6. 将新的二叉树添加到 list 中，为下一轮构建做准备
           nodes.add(parent);
       }

       // 返回赫夫曼树的 root 节点
       // 因为前面从小到大排序的，最后一个就是最大节点
       return nodes.get(0);
   }

测试输出，输出的是前序遍历的顺序。

结果和下图的前序遍历是一致的，如果不懂前序遍历请看数据结构与算法——二叉树

是不是有一个疑问？给定的数组是 13,7,8,3,29,6,1，变成树之后，怎么找回原来的数据？一定要记得赫夫曼树的特点：它的数据都在叶子节点，父节点是通过叶子节点相加得到的