Python数据结构之哈夫曼树定义与使用方法示例
发布时间:2020-12-16 21:03:23 所属栏目:Python 来源:网络整理
导读:本篇章节讲解Python数据结构之哈夫曼树定义与使用方法。供大家参考研究具体如下: HaffMan.py #coding=utf-8#考虑权值的haff曼树查找效率并非最高,但可以用于编码等使用场景下class TreeNode: def __init__(self,data): self.data=data self.left=
本篇章节讲解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,[8,[5,'F'],] tree.run(lis2) print tree.code(lis2) 运行结果: 更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》 希望本文所述对大家Python程序设计有所帮助。 您可能感兴趣的文章:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |