本文实例讲述了Python数据结构之哈夫曼树定义与使用方法。分享给大家供大家参考，具体如下：
HaffMan.py
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#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) |
运行结果：
希望本文所述对大家Python程序设计有所帮助。
原文链接：https://blog.csdn.net/sinat_33829806/article/details/78477076
