本文实例讲述了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)
运行结果：
