现有五个节点:A B C D E以及对应的权值,如何建立一颗huffman树进行哈夫曼编码?
基本思路:每次选取其中最小的两个权值的和作为左右节点,比如0.1+0.15=0.25,再从0.2,0.2,0.25,0.35中选取两个最小的,以此类推。编码的时候,从上往下,如果是左孩子就记为0,右孩子则记为1。
#定义树的结构 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]))
最后结果: