哈夫曼树简介
哈夫曼树，英文名huffman tree，它是一种的叶子结点带有权重的特殊二叉树，也叫最优二叉树。
哈夫曼（Huffman）编码是上个世纪五十年代由哈夫曼教授研制开发的，它借助了数据结构当中的树型结构，在哈夫曼算法的支持下构造出一棵最优二叉树，我们把这类树命名为哈夫曼树。
哈夫曼树核心
1）路径
在一棵树中，一个节点到另一个节点之间的通路，称为路径，如下图中的根节点到a之间的通路：
2）路径长度
在一条路径中，每经过一个节点，路径长度就加1，如上图根节点到节点c的路径长度为3：
3）节点的权
每个节点赋予一个新的数值，如a的权为7，b的权为5，如下图所示：
4）节点的带权路径长度
从根结点到该结点之间的路径长度与该结点的权的乘积，如下图所示：
如b的带权路径长度为2*5=10。
5）树的带权路径长度
树中所有叶子结点的带权路径长度之和，通常记作 “WPL” ，如下图中所示：
这颗树的带权路径长度为：WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3
赫夫曼树中有一个很重要的概念就是带权路径，带权路径最小的才是赫夫曼树，权值较大的结点离根较近。
哈夫曼树的特征
从定义和图上你也可以发现下面的规律：
- 初始节点都在树的叶子节点上；
- 权值大的节点离根更近；
- 每个非叶子节点都有两个孩子：因为我们自下向上构造，两个孩子构成一个新树的根节点。
哈夫曼树的构造
你可能会好奇一个哈夫曼树是怎么构造的，其实它是按照一个贪心思想和规则构造，而构造出来的这个树的权值最小。
基本步骤，大致分为如下3步：
1）从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树；
2）取出根节点权值最小的两颗二叉树，组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和；
3）再将这颗新的二叉树，以根节点的权值大小再次排序， 不断重复 1-2-3 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树。
下面我用图形的方式来还原构造过程。
1）初始构建森林
我们把每一个叶子结点，都当做树一颗独立的树，只有根结点的树，这样就形成了一个森林，如下图所示：
2）每次取两个最小权值顶点，构造父节点。
再将这颗新的二叉树，以根节点的权值大小 再次排序，如下图所示：
3）否不断重复上面的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树。
如下图所示：
最后，这棵哈夫曼树的WPL就为：
2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61
哈夫曼树代码实现
package 二叉树;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class HuffmanTree {
public static class node
{
int value;
node left;
node right;
int deep;//记录深度
public node(int value) {
this.value=value;
this.deep=0;
}
public node(node n1, node n2, int value) {
this.left=n1;
this.right=n2;
this.value=value;
}
}
private node root;//最后生成的根节点
List<node>nodes;
public HuffmanTree() {
this.nodes=null;
}
public HuffmanTree(List<node>nodes)
{
this.nodes=nodes;
}
public void createTree() {
Queue<node>q1=new PriorityQueue<node>(new Comparator<node>() {
public int compare(node o1, node o2) {
return o1.value-o2.value;
}});
q1.addAll(nodes);
while(!q1.isEmpty())
{
node n1=q1.poll();
node n2=q1.poll();
node parent=new node(n1,n2,n1.value+n2.value);
if(q1.isEmpty())
{
root=parent;return;
}
q1.add(parent);
}
}
public int getweight() {
Queue<node>q1=new ArrayDeque<node>();
q1.add(root);
int weight=0;
while (!q1.isEmpty()) {
node va=q1.poll();
if(va.left!=null)
{
va.left.deep=va.deep+1;va.right.deep=va.deep+1;
q1.add(va.left);q1.add(va.right);
}
else {
weight+=va.deep*va.value;
}
}
return weight;
}
public static void main(String[] args) {
List<node>list=new ArrayList<node>();
list.add(new node(2));
list.add(new node(3));
list.add(new node(6));
list.add(new node(8));list.add(new node(9));
HuffmanTree tree=new HuffmanTree();
tree.nodes=list;
tree.createTree();
System.out.println(tree.getweight());
}
}
作者简介
陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
👇阅读更多mikechen架构文章👇
阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师
以上
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》