快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹定義與使用方法示例

更新時(shí)間：2018年04月22日 12:16:22 作者：BUAA-XX

這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹定義與使用方法,結(jié)合具體實(shí)例形式分析了Python哈夫曼樹的原理、定義及簡單使用方法,需要的朋友可以參考下

本文實(shí)例講述了Python數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹定義與使用方法。分享給大家供大家參考，具體如下：

HaffMan.py

#coding=utf-8
#考慮權(quán)值的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)
      #結(jié)果與大話數(shù)據(jù)結(jié)構(gòu)書上略有不同 因?yàn)閘is[0][2]=lis[1][2] 無影響
      #這里使用parent 替代深度優(yōu)先/廣度優(yōu)先 算法
      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')
#應(yīng)用 HaffMan編碼,比如字母分布不均勻的情況下比較適合,可減少傳輸?shù)男畔⒘浚ǘM(jìn)制）,不會(huì)出現(xiàn)干涉。：
tree=HaffTree()
lis2=[
    [27,'A'],
    [8,'B'],
    [15,'C'],
    [15,'D'],
    [30,'E'],
    [5,'F'],
   ]
tree.run(lis2)
print tree.code(lis2)

運(yùn)行結(jié)果：