漫画：什么是 “哈夫曼树” ？
2020年04月20日 23:56 __ _ _ _ _
编者荐语：
给个小难题
以下文章来源于程序员小灰 ，作者小灰
程序员小灰. 全网70W+程序员粉丝，专注于编程、算法、AI、副业、个人成长的分享。**Success requires cost, time is also a kind of cost, the value of time is the
cost of saving.
**
成功需要成本，时间也是一种成本，对时间的珍惜就是对成本的节约。 往日精选： C语言IDE之Clion2020.1安装详解
以下为转载内容：
————— 第二天 —————
————————————
概念1：什么是路径？
在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。 ** **
上面的二叉树当中，从根结点A到叶子结点H的路径，就是A，B，D，H
概念2：什么是路径长度？
在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。
仍然用刚才的二叉树举例子，从根结点A到叶子结点H，共经过了3条边，因此路径长度是3
概念3：什么是 结点的带权路径长度？
树的每一个结点，都可以拥有自己的“权重”（Weight），权重在不同的算法当中可以起到不同的作用。
结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。
假设结点H的权重是3，从根结点到结点H的路径长度也是3，因此结点H的带权路径长度是 3 X 3 = 9
概念4：什么是 树的带权路径长度？
在一棵树中，所有 叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL 。
仍然以这颗二叉树为例，树的路径长度是 3X3 + 6X3 + 1X2 + 4X2 + 8X2 = 53
哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明，这到底是一颗什么样的树呢？
刚才我们学习了树的带权路径长度（WPL），而哈夫曼树（Huffman Tree）是 在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。
举个例子，给定权重分别为1，3，4，6，8的叶子结点，我们应当构建怎样的二叉树，才能保证其带权路径长度最小？
原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。
下图左侧的这棵树就是一颗哈夫曼树，它的WPL是46，小于之前例子当中的53：
需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗，下面这几棵树都是哈夫曼树：
假设有6个叶子结点，权重依次是2，3，7，9，18，25，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？
第一 步 ：构建森林
我们把每一个叶子结点，都当做树一颗独立的树（只有根结点的树），这样就形成了一个森林：
在上图当中，右侧是叶子结点的森林，左侧是一个辅助队列，按照权值从小到大存储了所有叶子结点。至于辅助队列的作用，我们后续将会看到。
第二 步 ：选择当前权值最小的两个结点，生成新的父结点
借助辅助队列，我们可以找到权值最小的结点2和3，并根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和：
第三 步 ：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列
也就是从队列中删除2和3，插入5，并且仍然保持队列的升序：
第四 步 ： 选择当前权值最小的两个结点，生成新的父结点 ** **
这是对第二步的重复操作。当前队列中权值最小的结点是5和7，生成新的父结点权值是5+7=12：
**第五 步 ：**从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 ** **
这是对第三步的重复操作， 也就是从队列中删除5和7，插入12 ，并且 仍然 保持队列的升序：
**第六 步 ：选择当前权值最小的两个结点，生成新的父结点 **
这是对第二步的重复操作。当前队列中权值最小的结点是9和12，生成新的父结点权值是9+12=21：
**第七 步 ：**从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 ** **
这是对第三步的重复操作，也就是从队列中删除9和12，插入21，并且仍然保持队列的升序：
**第八 步 ：选择当前权值最小的两个结点，生成新的父结点 **
这是对第二步的重复操作。当前队列中权值最小的结点是18和21，生成新的父结点权值是18+21=39：
**第九 步 ：**从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 ** **
这是对第三步的重复操作，也就是从队列中删除18和21，插入39，并且仍然保持队列的升序：
**第十 步 ：选择当前权值最小的两个结点，生成新的父结点 **
这是对第二步的重复操作。当前队列中权值最小的结点是25和39，生成新的父结点权值是25+39=64：
**第十一 步 ：**从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 ** **
这是对第三步的重复操作，也就是从队列中删除25和39，插入64 ：
此时，队列中仅有一个结点，说明整个森林已经合并成了一颗树，而这棵树就是我们想要的哈夫曼树：
1. private Node root;
2. private Node[] nodes;
3.
4. //构建哈夫曼树
5. public void createHuffman(int[] weights) {
6. //优先队列，用于辅助构建哈夫曼树
7. Queue<Node> nodeQueue = new PriorityQueue<>();
8. nodes = new Node[weights.length];
9.
10. //构建森林，初始化nodes数组
11. for(int i=0; i<weights.length; i++){
12. nodes[i] = new Node(weights[i]);
13. nodeQueue.add(nodes[i]);
14. }
15.
16. //主循环，当结点队列只剩一个结点时结束
17. while (nodeQueue.size() > 1) {
18. //从结点队列选择权值最小的两个结点
19. Node left = nodeQueue.poll();
20. Node right = nodeQueue.poll();
21. //创建新结点作为两结点的父节点
22. Node parent = new Node(left.weight + right.weight, left, right);
23. nodeQueue.add(parent);
24. }
25. root = nodeQueue.poll();
26. }
27.
28. //按照前序遍历输出
29. public void output(Node head) {
30. if(head == null){
31. return;
32. }
33. System.out.println(head.weight);
34. output(head.lChild);
35. output(head.rChild);
36. }
37.
38. public static class Node implements Comparable<Node>{
39. int weight;
40. Node lChild;
41. Node rChild;
42.
43. public Node(int weight) {
44. this.weight = weight;
45. }
46.
47. public Node(int weight, Node lChild, Node rChild) {
48. this.weight = weight;
49. this.lChild = lChild;
50. this.rChild = rChild;
51. }
52.
53. @Override
54. public int compareTo(Node o) {
55. return new Integer(this.weight).compareTo(new Integer(o.weight));
56. }
57. }
58.
59. public static void main(String[] args) {
60. int[] weights = {2,3,7,9,18,25};
61. HuffmanTree huffmanTree = new HuffmanTree();
62. huffmanTree.createHuffman(weights);
63. huffmanTree.output(huffmanTree.root);
64. }
在这段代码中，为了保证结点队列当中的结点始终按照权值升序排列，我们使用了优先队列 PriorityQueue 。
与此同时，静态内部类Node需要实现比较接口，重写 compareTo 方法，以保证Node对象在进入队列时按照权值来比较。
本文著作权归原作者所有，如需转载，请联系原作者。
今天为大家推荐一个与数据结构相关的知识，可以认真琢磨哦。
** 往期推荐： C语言IDE之Clion2020.1安装详解2020-04-15
给IT技术爱好者的一封信2020-04-12
基于结构体的学生信息管理系统2020-04-19
公众号：程序员Bob一个正在学习C语言的人，致力于将C讲得更透彻！点赞关注谢谢你长按下图二维码关注，和你一起领悟程序员的魅力。**
点个[在看]，是对小Bob最大的支持！
预览时标签不可点
__
