现有五个节点：A B C D E以及对应的权值，如何建立一颗huffman树进行哈夫曼编码?
基本思路：每次选取其中最小的两个权值的和作为左右节点，比如0.1 0.15=0.25，再从0.2，0.2，0.25，0.35中选取两个最小的，以此类推。编码的时候，从上往下，如果是左孩子就记为0，右孩子则记为1。
代码语言：javascript复制#定义树的结构
class Node:
def __init__(self,freq):
self.left = None
self.right = None
self.parent = None
self.freq =freq
def isLeft(self):
return self.parent.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 x:x.freq)
#前两个最小的值出队列
node_left=queue.pop(0)
node_right = queue.pop(0)
node_parent=Node(node_left.freq node_right.freq)
node_parent.left=node_left
node_parent.right=node_right
node_left.parent = node_parent
node_right.parent=node_parent
#生成新的节点，放到队列后
queue.append(node_parent)
#队列中最后剩下的元素就是根节点
queue[0].parent=None
return queue[0]
def huffmanEncoding(nodes,root):
#用于存储每个节点的编码值
codes=['']*len(nodes)
for i in range(len(nodes)):
#第i个节点
node_temp=nodes[i]
while node_temp !=root:
if node_temp.isLeft():
#如果是左节点就加‘0’
codes[i]='0' codes[i]
else:
#否则加‘1’
codes[i]='1' codes[i]
node_temp=node_temp.parent
return codes
letters_freqs=[('B',10),('E',15),('C',20),('D',20),('A',35)]
nodes = createNodes([item[1] for item in letters_freqs])
root = createHuffmanTree(nodes)
codes = huffmanEncoding(nodes,root)
for item in zip(letters_freqs,codes):
print("better:{} freq:{} HuffmanCode:{}".format(item[0][0],item[0][1],item[1]))最后结果：
