Huffman树是一种特殊结构的二叉树，由Huffman树设计的二进制前缀编码，也称为Huffman编码在通信领域有着广泛的应用。在word2vec模型中，在构建层次Softmax的过程中，也使用到了Huffman树的知识。

在通信中，需要将传输的文字转换成二进制的字符串，假设传输的报文为：“AFTERDATAEARAREARTAREA”，现在需要对该报文进行编码。

一、Huffman树的基本概念

在二叉树中有一些基本的概念，对于如下所示的二叉树：

• 路径

路径是指在一棵树中，从一个节点到另一个节点之间的分支构成的通路，如从节点8到节点1的路径如下图所示：

• 路径长度

路径长度指的是路径上分支的数目，在上图中，路径长度为2。

• 节点的权

节点的权指的是为树中的每一个节点赋予的一个非负的值，如上图中每一个节点中的值。

• 节点的带权路径长度

节点的带权路径长度指的是从根节点到该节点之间的路径长度与该节点权的乘积：如对于1节点的带权路径长度为：2。

• 树的带权路径长度

树的带权路径长度指的是所有叶子节点的带权路径长度之和。

有了如上的概念，对于Huffman树，其定义为：

给定nn权值作为nn个叶子节点，构造一棵二叉树，若这棵二叉树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为Huffman树。

由以上的定义可以知道，Huffman树是带权路径长度最小的二叉树，对于上面的二叉树，其构造完成的Huffman树为：

二、Huffman树的构建

由上述的Huffman树可知：节点的权越小，其离树的根节点越远。那么应该如何构建Huffman树呢？以上述报文为例，首先需要统计出每个字符出现的次数作为节点的权:

接下来构建Huffman树：

• 重复以下的步骤：
  

• • 按照权值对每一个节点排序：D-F-T-E-R-A

  • 选择权值最小的两个节点，此处为D和F生成新的节点，节点的权重为这两个节点的权重之和，为2

• 直到只剩最后的根节点

按照上述的步骤，该报文的Huffman树的生成过程为：

三、由Huffman树生成Huffman编码

有了上述的Huffman树的结构，现在我们需要利用Huffman树对每一个字符编码，该编码又称为Huffman编码，Huffman编码是一种前缀编码，即一个字符的编码不是另一个字符编码的前缀。在这里约定：

• 将权值小的最为左节点，权值大的作为右节点

• 左孩子编码为0，右孩子编码为1

因此，上述的编码形式如下图所示：

从上图中，E节点的编码为：00，同理，D节点的编码为1001

其最终的结果为：