贪心法--哈夫曼编码

概述现有五个节点：A B C D E以及对应的权值，如何建立一颗huffman树进行哈夫曼编码? 基本思路：每次选取其中最小的两个权值的和作为左右节点，比如0.1ʰ.15=0.25，再从0.2，0.2，

现有五个节点：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生成节点列表 createNodes(freqs):    return [Node(freq) for freq in freqs] 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] huffmanEnCoding(nodes,root):    用于存储每个节点的编码值    codes=['']*len(nodes)    for i  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]=1codes[i]            node_temp=node_temp.parent     codesletters_freqs=[(B',10),(ECDA)]nodes = createNodes([item[1] for item  letters_freqs])root = createHuffmanTree(nodes)codes = zip(letters_freqs,codes):    print("better:{} freq:{} HuffmanCode:{}".format(item[0][0],item[0][1],item[1]))

最后结果：

总结

以上是内存溢出为你收集整理的贪心法--哈夫曼编码全部内容，希望文章能够帮你解决贪心法--哈夫曼编码所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。