本文实例讲述了Python数据结构之哈夫曼树定义与使用方法。分享给大家供大家参考，具体如下：

HaffMan.py

#coding=utf-8#考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=Noneclass HaffTree: def __init__(self): self.root=None def set_root(self,rootNode): self.root=rootNode def run(self,lis): i=0 lis=[[lis[j][0],lis[j][1],TreeNode(lis[j][1])]for j in range(len(lis))] while len(lis)>1: i+=1 lis=sorted(lis) name='N'+str(i) temp=TreeNode(name) #结果与大话数据结构书上略有不同 因为lis[0][2]=lis[1][2] 无影响 #这里使用parent 替代深度优先/广度优先 算法 temp.left=lis[0][2] temp.right=lis[1][2] lis[0][2].parent=temp lis[1][2].parent=temp #print lis[0][0],lis[1][0],len(lis) value=lis[0][0]+lis[1][0] lis=lis[1:] lis[0]=[value,name,temp] #print temp.data,temp.left.data,temp.right.data self.set_root(temp) def code(self,lis): self.codeList=[] stack=[] Node=self.root stack.append(Node) res=[] while(stack): node=stack.pop() res.append(node) if node.right: stack.append(node.right) if node.left: stack.append(node.left) for li in lis: codeL=[] for re in res: if re.data==li[1]: parent=re print '\n',parent.data, codeL.append(parent) while parent.parent: parent=parent.parent print parent.data, codeL.append(parent) codeLL=[int(codeL[len(codeL)-2-i]==codeL[len(codeL)-1-i].right) for i in range(len(codeL)-1)] self.codeList.append([li[1],codeLL]) return self.codeList def list_all(self,method): lis=[] res=[] if method=='before': Node=self.root lis.append(Node) while(lis): node=lis[-1] lis=lis[:-1] if node: res.append(node.data) if node.right: lis.append(node.right) if node.left: lis.append(node.left) elif method=='mid': node = self.root while lis or node: while node: lis.append(node) node = node.left if len(lis)>0: node = lis[-1] lis=lis[:-1] if node: res.append(node.data) node= node.right else: pass return res

HaffMantest.py

#coding=utf-8from HaffMan import HaffTreetree=HaffTree()lis=[ [5,'A'], [15,'B'], [40,'C'], [30,'D'], [10,'E'], ]print lis[2:]print sorted(lis)tree.run(lis)print tree.list_all('before')#应用 HaffMan编码,比如字母分布不均匀的情况下比较适合,可减少传输的信息量（二进制）,不会出现干涉。：tree=HaffTree()lis2=[ [27,'A'], [8,'B'], [15,'C'], [15,'D'], [30,'E'], [5,'F'], ]tree.run(lis2)print tree.code(lis2)

运行结果：

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。