什么是合适的鞋垫树：
给出n个权重作为n个叶的节点，构造一棵二叉树。 如果该树的加权路径长度最小，则将这种二叉树称为最佳二叉树，也称为适当的鞋垫树(Huffman Tree )。 合适的鞋垫树是权重路径长度最短的树，权重大的节点接近根。
为了进行适当的控制台代码，使用了适当的控制台树。 为您介绍合适的控制台代码：
将发送的电文设为“ABACCDA”。 这只有四种字符，可以用两个字符的字符串来区分。 假设a、b、c、d的代码分别为00、01、10、11，则该电文的代码为“00010010101100”，全长为14位。 对方收到的时候，在现实中，代码总长最好尽量短，但是如果每个文字采用设计长度不同的代码，电文中出现次数多的文字尽量短的代码，就可以减少电文总长。 例如，如果设计a、b、c、d的代码为0，00，1，01，则上述电文可以变换为“000011010”，全长9。 但是，这样的电文是不能翻译的。 例如，“0000”有多个译文。 要设计不同长度的代码，其中一个字符的代码必须是前缀，而不是另一个字符的代码，因为它可以是" AAAA "、" ABA "或" BB "。 将此代码转换为前缀编码
那么，如何得到电文长度最短的二进制前缀码？ 设计电文全长最短的二进制前缀码是以n种字符出现的频率为权重来设计相应的鞋垫树的问题，由此得到的二进制前缀码称为合适的鞋垫码。
让我们看看如何做赫夫曼树。
对于如何构造合适的鞋垫树，合适的鞋垫最早给出了具有一般规律的算法，俗称合适的鞋垫算法：
(1)根据给定的n个权重(w1w1，w 2 w_2 w2 ……，w n w_n wn } )构成n个二叉树的集合f=(t1t1，T 2 T_2 T2 ……，T n T_n Tn } )，其中的每一个二分
)2)在f中，将2棵根节点权重最小的树作为左右子树构成1棵新的二叉树，并且将新二叉树的根节点的权重作为其左右子树中根节点的权重之和。
)3)用f删除这两棵树，同时将新得到的二叉树添加到f中；
重复(4) )和(3)的步骤，直到f中只含有一棵树。 这棵树是合适的鞋垫树。
让我们来看看简单的情况。字母{a,b,c,d}，出现的次数为{7,5,2,4},构建出合适的鞋垫树：
我们按照合适的鞋垫算法来构建合适的鞋垫树。
第一步，选择在二叉树中构建最小的两个。
步骤2在权重序列中添加6，并删除前面的2和4。
权重列表为{7、5、6}
重复步骤1和2，直到生成完成。
权重列表： { 7，11 }
这样就完成了相应的鞋垫构建：
带通的长度为wpl=7x 1、5x 2、2x 3、4x3=35
当然，合适的鞋垫树不是唯一的。 例如，上面合适的鞋
垫树也可以为：带权路径长度为：WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35
但是不管合适的鞋垫树怎样构造，最短带权路径长度只有一个。
由于合适的鞋垫树中没有度为1的结点（又叫做正则二叉树），则一棵有n个叶子结点的合适的鞋垫树共有2n-1个结点，可以存储在哎一个大小为2n-1的一维数组中。
下面来看一个复杂的例题：
已知某系统的通信联络中只可能出现8中字符，次数别为w= {5，29，7，8，14，23，3，11}
按照合适的鞋垫算法来构建合适的鞋垫树：
权值列表：{3，5，7，8，11，14，23，29}
权值列表：{7，8，8，11，14，23，29}
权值列表：{8，11，14，15，23，29}
权值列表：{14，15，19，23，29}
权值列表：{19，23，29，29}
权值列表：{29，29，42}
权值列表：{42，58}
至此，合适的鞋垫树已经构建完成。我们来算算其带权路径：
WPL = 23x2 + 11x3 + 5x4 + 3x4 + 29x2 + 14x3 + 7x4 + 8x4 = 271
我们规定向左为0，向右为1，则，该合适的鞋垫树为：
则这八种字符的编码分别为：{0110，10，1110，1111，110，00，011，010}
当然构造出的合适的鞋垫树不止一种，也可能为：
该图的带权路径为:
WPL = 29x2 + 14x3 + 7x4 + 3x5 + 5x5 + 23x2 + 8x3 + 11x3 = 271
由此看出，合适的鞋垫树可能不同，但是带权路径一定是同一个最小值。
已经了解了思想了，现在该如何实现了。
class Node: def __init__(self, name, weight): self.name = name #节点名 self.weight = weight #节点权重 self.left = None #节点左孩子 self.right = None #节点右孩子 self.father = None # 节点父节点 #判断是否是左孩子 def is_left_child(self): return self.father.left == self#创建最初的叶子节点def create_prim_nodes(data_set, labels): if(len(data_set) != len(labels)): raise Exception('数据和标签不匹配!') nodes = [] for i in range(len(labels)): nodes.append( Node(labels[i],data_set[i]) ) return nodes# 创建huffman树def create_HF_tree(nodes): #此处注意，copy()属于浅拷贝，只拷贝最外层元素，内层嵌套元素则通过引用，而不是独立分配内存 tree_nodes = nodes.copy() while len(tree_nodes) > 1: #只剩根节点时，退出循环 tree_nodes.sort(key=lambda node: node.weight)#升序排列 new_left = tree_nodes.pop(0) new_right = tree_nodes.pop(0) new_node = Node(None, (new_left.weight + new_right.weight)) new_node.left = new_left new_node.right = new_right new_left.father = new_right.father = new_node tree_nodes.append(new_node) tree_nodes[0].father = None #根节点父亲为None return tree_nodes[0] #返回根节点#获取huffman编码def get_huffman_code(nodes): codes = {} for node in nodes: code='' name = node.name while node.father != None: if node.is_left_child(): code = '0' + code else: code = '1' + code node = node.father codes[name] = code return codesif __name__ == '__main__': labels = ['A','B','C','D','E','F','G','H'] data_set = [5,29,7,8,14,23,3,11] nodes = create_prim_nodes(data_set,labels)#创建初始叶子节点 root = create_HF_tree(nodes)#创建huffman树 codes = get_huffman_code(nodes)#获取huffman编码 #打印huffman码 for key in codes.keys(): print(key,': ',codes[key])运行结果：
A : 0001B : 10C : 1110D : 1111E : 110F : 01G : 0000H : 001代码参考自：合适的鞋垫树代码