Python数据结构之哈夫曼树定义与使用方法示例

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

本文实例讲述了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,[8,[5,'F'],]tree.run(lis2)print tree.code(lis2)

运行结果：

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

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

您可能感兴趣的文章:python数据结构之图深度优先和广度优先实例详解python数据结构之图的实现方法Python数据结构与算法之图结构（Graph）实例分析Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例Python数据结构与算法之图的广度优先与深度优先搜索算法示例Python数据结构与算法之图的基本实现及迭代器实例详解Python数据结构之双向链表的定义与使用方法示例Python数据结构与算法之使用队列解决小猫钓鱼问题Python数据结构与算法之二叉树结构定义与遍历方法详解Python数据结构之图的应用示例 总结

以上是内存溢出为你收集整理的Python数据结构之哈夫曼树定义与使用方法示例全部内容，希望文章能够帮你解决Python数据结构之哈夫曼树定义与使用方法示例所遇到的程序开发问题。

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