現有五個節點:A B C D E以及對應的權值,如何建立一顆huffman樹進行哈夫曼編碼?
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5iNjNmNkN2NwY2NyYDZygTNzQ2YlRmM0MGZ1IWOwQ2Mk9CX3AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLzM3Lc9CX6MHc0RHaiojIsJye.png)
#定義樹的結構
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]))
最後結果: