哈夫曼树
哈夫曼树又称为最优树、最优二叉树
相关概念
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。如图1，从根结点到结点 a 之间的通路就是一条路径。
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。
哈夫曼树.png
构建哈夫曼树
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
1.在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
2.在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
3.重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
构建哈夫曼树的过程.png
哈弗曼树中的查找算法
构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。
查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：
- 如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
- 如果介于两个结点权重值之间，替换原来较大的结点；
哈夫曼编码
哈夫曼编码就是在哈夫曼树的基础上构建的，这种编码方式最大的优点就是用最少的字符包含最多的信息内容。
根据发送信息的内容，通过统计文本中相同字符的个数作为每个字符的权值，建立哈夫曼树。对于树中的每一个子树，统一规定其左孩子标记为 0 ，右孩子标记为 1 。这样，用到哪个字符时，从哈夫曼树的根结点开始，依次写出经过结点的标记，最终得到的就是该结点的哈夫曼编码。文本中字符出现的次数越多，在哈夫曼树中的体现就是越接近树根。编码的长度越短。
哈夫曼编码
如图所示，字符 a 用到的次数最多，其次是字符 b 。字符 a 在哈夫曼编码是 0 ，字符 b 编码为 10 ，字符 c 的编码为 110 ，字符 d 的编码为 111 。
使用程序求哈夫曼编码有两种方法：
*1. 从叶子结点一直找到根结点，逆向记录途中经过的标记。例如，图 3 中字符 c 的哈夫曼编码从结点 c 开始一直找到根结点，结果为：0 1 1 ，所以字符 c 的哈夫曼编码为：1 1 0（逆序输出）。
- 从根结点出发，一直到叶子结点，记录途中经过的标记。例如，求图 3 中字符 c 的哈夫曼编码，就从根结点开始，依次为：1 1 0。*
哈夫曼树实现字符进行哈夫曼编码：
参考博客：https://blog.csdn.net/sinat_16968575/article/details/44625743
为简单起见，本文代码假设已经统计好字符以及出现的次数，将其保存在一个数组中，在这样的情况下对数据进行编码
# 本代码哈夫曼树的构建包括 定义节点类、创建叶子结点、创建哈夫曼树、哈夫曼编码四部分
# 本文假定已经统计好字符以及字符的出现子树信息
class Node:
def __init__(self,freqs):
self.left = None
self.right = None
self.father = None
self.freqs = freqs
def isLeft(self): # 判断是否为左子节点
return self.father.left == self
# 创建叶子节点
def CreateNodes(freqs):
return [Node(freq) for freq in freqs]
# 创建哈夫曼树，通过该函数将节点中的属性确定，建立书结构
def CreateHuffmanTree(nodes):
queue = nodes[:] # 所有节点
while len(queue) > 1:
queue.sort(key = lambda item:item.freqs) #lambda 第一个参数是传入的变量，冒号后面的是返回的值
node_left = queue.pop(0)
node_right = queue.pop(0)
#建立树
node_father = Node(node_left.freqs+node_right.freqs)
node_father.left = node_left
node_father.right = node_right
node_left.father = node_father
node_right.father = node_father
queue.append(node_father)
queue[0].father = None # 根节点没有父节点
return queue[0]
# 哈夫曼编码
def HufmanCoding(nodes,root):
codes = ['']*len(nodes)
for i in range(len(nodes)): #对于每一叶子节点自下而上进行回溯，编码，直到到根节点
node_tmp = nodes[i]
print(nodes[i])
while node_tmp != root:
if node_tmp.isLeft():
codes[i]= '0'+ codes[i]
print(codes[i])
else:
codes[i]='1' + codes[i]
node_tmp = node_tmp.father
return codes
chars_freqs = [('C', 2), ('G', 2), ('E', 3)]
nodes = CreateNodes([item[1] for item in chars_freqs])
print(nodes)
root = CreateHuffmanTree(nodes)
codes = HufmanCoding(nodes,root)
for item in zip(chars_freqs,codes):
print('Character:%s freq:%-2d encoding: %s' % (item[0][0],item[0][1],item[1]))
代码运行结果.png
