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

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

2021-02-04 00:23BUAA-XX Python

这篇文章主要介绍了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=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)