哈弗曼树往往都会根据哈夫曼编码结合着来说，因此这篇文章，主要结合着面试问题来说明。

一、基本概念

哈夫曼树的目的是找出存放一串字符所需的最少的二进制编码， 原理是通过统计出每种字符出现的频率！不断地对其合并。

举个例子：有一串字符，现在把这些字符进行统计，频率表 A：60, B:45, C:13 D:69 E:14 F:5 G:3。现在要对这些字符进行编码，但是前提是使用最少的二进制编码。这时候怎么办呢？这就用到了我们的哈弗曼树。

我们需要构造一个哈弗曼树，构造赫夫曼树的算法是一个贪心算法，贪心的地方在于：总是选取当前频率(权值)最低的两个结点来进行合并，构造新结点。

现在我们就来构造一颗哈弗曼树。

二、构造哈弗曼树

刚刚我们已经说了，构造哈夫曼树是每次选取当前频率最低的两个节点来进行合并就好了。

1、原始序列

2、选取最小的F和G节点合并

3、选取目前最小的C节点与8合并

4、继续重复以上步骤进行合并

到此为止，我们的哈弗曼树就已经构造出来了。接下来我们添加01规则，进行哈夫曼编码。

三、哈夫曼编码

哈夫曼编码的规则是，左边添加0，右边添加1。看下图就明白了。

OK，也就是在每一条边上添加了01。此时我们来看每一个字符的编码。

A：10 B：01 C：0011 D：11 E：000 F：00101 G：00100

四、java实现哈夫曼编码

我们直接给出一个整体的哈夫曼编码的java实现。

第一步：定义一个节点

第二步：实现哈夫曼编码

​