十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
这篇文章给大家分享的是有关Python数据结构之哈夫曼树的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
HaffMan.py
#coding=utf-8 #考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下 class TreeNode: def __init__(self,data): self.data=data self.left=None self.right=None self.parent=None class 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-8 from HaffMan import HaffTree tree=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数据结构之哈夫曼树的示例分析”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!