哈夫曼树实现 python

参考博客：

Http://linux.xidian.edu.cn/bbs/thread-70-1-1.html

基本上相当于抄写一遍了。。呃呃。。。。。

import heapq
def make_hufftree(inlist):
    trees=list(inlist)
    heapq.heapify(trees)
    while len(trees)>1:
        rightChild,leftChild=heapq.heappop(trees),heapq.heappop(trees)
        parentnode=(leftChild[0]+rightChild[0],leftChild,rightChild)
        heapq.heappush(trees,parentNode)
    return trees[0]
def encodehufftree(curNode,codelist,pref=''):
    if len(curNode)==2:
        codelist.append((curNode[1],pref))
    else:
        encodehufftree(curNode[1],codelist,pref+'0')
        encodehufftree(curNode[2],codelist,pref+'1')
def printcode(codelist):
    for item in codelist:
        print item[0],item[1]
exampleData = [
    (0.125 , 'aaa'),
    (0.075 , 'aab'),
    (0.050 , 'aac'),
    (0.075 , 'aba'),
    (0.045 , 'abb'),
    (0.030 , 'abc'),
    (0.050 , 'aca'),
    (0.030 , 'acb'),
    (0.020 , 'acc'),
    (0.075 , 'baa'),
    (0.045 , 'bab'),
    (0.030 , 'bac'),
    (0.045 , 'bba'),
    (0.027 , 'bbb'),
    (0.018 , 'bbc'),
    (0.060 , 'bca'),
    (0.018 , 'bcb'),
    (0.012 , 'bcc'),
    (0.050 , 'caa'),
    (0.030 , 'cab'),
    (0.020 , 'cac'),
    (0.030 , 'cba'),
    (0.018 , 'cbb'),
    (0.012 , 'cbc'),
    (0.020 , 'cca'),
    (0.012 , 'ccb'),
    (0.008 , 'ccc')
  ]
hufftree=make_hufftree(exampleData)
codelist=[]
encodehufftree(hufftree,codelist)
codelist.sort(key=lambda x:x[0])
printcode(codelist)