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,'A'],    [8,'B'],    [15,'C'],    [15,'D'],    [30,'E'],    [5,'F'],   ]tree.run(lis2)print tree.code(lis2)