在一颗树中，从一个节点到另一个节点所经过的所有节点，就是两个节点的路径
上面的二叉树当中，从根结点A到叶子结点H的路径，就是A，B，D，H。
从根结点A到叶子结点H，共经过了3条边，因此路径长度是3。
树的每一个结点，都可以拥有自己的“权重”（Weight），权重在不同的算法当中可以起到不同的作用。
结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。 假设结点H的权重是3，从根结点到结点H的路径长度也是3，因此结点H的带权路径长度是 3 X 3 = 9。
在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为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，如何构建一颗哈夫曼树，也就是带权路径长度最小的树呢？ 第1步：构建森林 我们把每一个叶子节点，都当作是一颗独立的树（只有根节点的树），这样就形成了一个森林。
在上图中，右侧是叶子节点的森林，左侧是一个辅助队列，按照权值从小到大存储着所有叶子节点。至于辅助队列的作用，我们后续将会看到。
第2步：选择当前权值最小的两个节点，生成新的父节点
借助辅助队列，我们可以找到权值最小的节点2和3，并根据这两个节点生成一个新的父节点，父节点的权值是这两个节点权值之和
第3步：从队列中移除上一步选择的两个最小节点，把新父节点加入队列
也就是从队列中删除2和3，插入5，并且仍然保持队列的升序：
第4步：选择当前权值最小的两个结点，生成新的父结点 这是对第2步的重复操作。当前队列中权值最小的结点是5和7，生成新的父结点权值是5+7=12：
第5步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 这是对第3步的重复操作，也就是从队列中删除5和7，插入12，并且仍然保持队列的升序： 第6步：选择当前权值最小的两个结点，生成新的父结点 这是对第2步的重复操作。当前队列中权值最小的结点是9和12，生成新的父结点权值是9+12=21
第7步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 这是对第3步的重复操作，也就是从队列中删除9和12，插入21，并且仍然保持队列的升序：
第8步：选择当前权值最小的两个结点，生成新的父结点 这是对第2步的重复操作。当前队列中权值最小的结点是18和21，生成新的父结点权值是18+21=39： 第9步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 这是对第3步的重复操作，也就是从队列中删除18和21，插入39，并且仍然保持队列的升序： 第10步：选择当前权值最小的两个结点，生成新的父结点 这是对第2步的重复操作。当前队列中权值最小的结点是25和39，生成新的父结点权值是25+39=64： 第11步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列 这是对第3步的重复操作，也就是从队列中删除25和39，插入64
此时，队列中仅有一个结点，说明整个森林已经合并成了一颗树，而这棵树就是我们想要的哈夫曼树：
哈夫曼编码是一种高效的编码方式，在信息存储和传输过程中，用于对信息的压缩
那么霍夫曼编码是怎么进行信息压缩的呢？我们先来学习下计算机是怎么存储信息的
计算机不是人，它不认识中文和英文，更不认识图片和视频，它唯一“认识”的就是0（低电平）和1（高电平）。
因此，我们在计算机上看到的一切文字、图像、音频、视频，底层都是用二进制来存储和传输的。
从狭义上来讲，把人类能看懂的各种信息，转换成计算机能够识别的二进制形式，被称为编码。
编码的方式可以有很多种，我们大家最熟悉的编码方式就属ASCII码了。
在ASCII吗中，把每一个字符当成是一个特定的8位二进制数，比如 显然，ASCII码是一种等长编码，也就是任何字符的编码长度都相等。
等长编码的优缺点：
优点：容易设计，方便读写缺点：可能会占用过多资源为什么这么说呢？让我们来看一个例子：
假如一段信息当中，只有A，B，C，D，E，F这6个字符，如果使用等长编码，我们可以把每一个字符都设计成长度为3的二进制编码：
如此一来，给定一段信息 “ABEFCDAED”，就可以编码成二进制的 “000 001 100 101 010 011 000 100 011”，编码总长度是27。 但是，这样的编码方式是最优的设计吗？如果我们让不同的字符对应不同长度的编码，结果会怎样呢？比如： 如此一来，给定的信息 “ABEFCDAED”，就可以编码成二进制的 “0 00 10 11 01 1 0 10 1”，编码的总长度只有14。 对于不定长编码，如果一个字符的编码刚好是另一个字符编码的前缀，就会带来歧义问题。这个时候，哈夫曼编码出场了。
哈夫曼编码(Huffman Coding)也是一种不定长编码，由麻省理工学院的哈夫曼博所发明，这种编码方式实现了两个重要目标：
1.任何一个字符编码，都不是其他字符编码的前缀。 2.信息编码的总长度最小。
哈夫曼编码的生成过程（通过哈夫曼树实现的）是什么样子呢？让我们看看下面的例子：
假如一段信息里只有A，B，C，D，E，F这6个字符，他们出现的次数依次是2次，3次，7次，9次，18次，25次，如何设计对应的编码呢？
我们不妨把这6个字符当做6个叶子结点，把字符出现次数当做结点的权重，以此来生成一颗哈夫曼树： 这样做的意义是什么呢？
哈夫曼树的每一个结点包括左、右两个分支，二进制的每一位有0、1两种状态，我们可以把这两者对应起来，结点的左分支当做0，结点的右分支当做1，会产生什么样的结果？ 这样一来，从哈夫曼树的根结点到每一个叶子结点的路径，都可以等价为一段二进制编码： 上述过程借助哈夫曼树所生成的二进制编码，就是哈夫曼编码。
现在，我们面临两个关键的问题：
首先，这样生成的编码有没有前缀问题带来的歧义呢？答案是没有歧义。
因为每一个字符对应的哈夫曼树的叶子节点，从根节点到这些叶子节点的路径并没有包含关系，最终得到的二进制编码自然也不会是彼此的前缀其次，这样生成的编码能保证总长度最小吗？答案是可以保证。
哈夫曼树的重要特性，就是所有叶子结点的（权重 X 路径长度）之和最小。放在信息编码的场景下，叶子结点的权重对应字符出现的频次，结点的路径长度对应字符的编码长度。所有字符的（频次 X 编码长度）之和最小，自然就说明总的编码长度最小。使用哈夫曼编码得到的编码总长度，比使用定长编码短了多少？
