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

yipeiwu_com6年前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=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相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总

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

相关文章

Python实现读取json文件到excel表

本文实例为大家分享了Python实现读取json文件到excel表,供大家参考,具体内容如下 一、需求 1、'score.json' 文件内容: { "1":["小花",99,1...

python脚本监控docker容器

本文实例为大家分享了python脚本监控docker容器的方法,供大家参考,具体内容如下 脚本功能: 1、监控CPU使用率 2、监控内存使用状况 3、监控网络流量 具体代码: #!/...

详解Django rest_framework实现RESTful API

详解Django rest_framework实现RESTful API

一、什么是REST 面向资源是REST最明显的特征,资源是一种看待服务器的方式,将服务器看作是由很多离散的资源组成。每个资源是服务器上一个可命名的抽象概念。因为资源是一个抽象的概念,所以...

使用python+whoosh实现全文检索

whoosh的官方介绍:http://whoosh.readthedocs.io/en/latest/quickstart.html 因为做的是中文的全文检索需要导入jieba工具包以及...

Python imread、newaxis用法详解

这篇文章主要介绍了python imread、newaxis用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一:imread...