python哈夫曼树_python霍夫曼树

class Node():

data=0

left=None

right=None

father=None

def __init__(self,data,left,right):

self.data=data

self.left=left

self.right=right

这里定义了一个Node类

声明了左右结点和父节点,父节点是用来输出霍夫曼编码用的。

初始化构造函数，给数据和左右结点赋值,父节点不在这初始化,self的话和this关键字差不多

root=None

声明根节点

def zhuanhuan( arr,index,n):

if index>=len(arr):

return None

else:

left=Node(arr[index],None,None)

num1=arr[index]+n.data

node=Node(num1,left,n)

left.father=node

n.father=node

if index==0:

index+=1

if index==len(arr)-1:

global root

root=node

zhuanhuan(arr,index+1,node)

这是一个转换函数,把数组转化为霍夫曼树,传入的形参 arr是数组,index是下标,n是结点(定义结点是为了避免几个结点断节)

如果index大于数组的长度,那么就退出

如果小于就继续构建霍夫曼树

根据霍夫曼树的构建原理,传入一个数组的值,把二者和的结点的传入构造函数,递归，

left=Node(arr[index],None,None)

num1=arr[index]+n.data

node=Node(num1,left,n)

中间就是利用构造函数初始化的代码

left.father=node

n.father=node

把左右结点的父节点指向node

因为数组是从0开始到len(arr)-1

所以当index满足 if index==len(arr)-1:时

就定义一个全局root作为根节点

global  root

root=node

然后递归zhuanhuan(arr,index+1,node)

flag=False

v=[]

声明一个标志,定义一个bool型数组

for i in range(100):

v.append(False)

初始化100个False

输出霍夫曼编码函数

def show(n):

global flag 全局标志

global arm 记录个数的数组

global ard 记录字符串不同的字符

if n!=None: 如果结点不为空

if (n.left==None and n.right==None)or flag==True://如果是叶子结点或者遍历父节点

if v[n.data]!=True and(n.left==None and n.right==None)://如果叶子结点没有输出过

for i in range(len(arm))://把数字转化为原来的字符码比如a出现了4次那么在霍夫曼树记录的就是4,这个循环就是把4再转化为a

if n.data==arm[i]:

print ard[i],":",

break

if n.father==None://如果父节点为空 那么就代表遍历可以结束了

flag=False;

return

else://如果父节点不为空就继续循环遍历

flag=True标志设为

show(n.father)//遍历父节点

if n==n.father.right:如果是右子树就输出1

print 1," ",

else://如果是左子树就输出0

print 0," ",

else:如果不是叶子结点就递归遍历霍夫曼树

show(n.left)

show(n.right)

print "请输入一段字符串:"

str=raw_input()

arr=[]#字符数组

arr=str

ard=[]//记录有几个不同字符的数组

for i in range(len(arr))://把不同的字符放入ard字符数组

flag=True

for j in range(len(ard)):

if ard[j]==arr[i]:

flag=False;

break

if flag!=False:

ard.append(arr[i])

arm=[]//权值数组

for i in range(len(ard))://更新权值

arm.append(0)

for i in range(len(arr)):

for j in range(len(ard)):

if arr[i]==ard[j]://每出现一次那个字符的权值层数组就自增1

arm[j]+=1;

break

for i in range(len(ard)-1)://插入排序

temp=ard[i+1]//记录下一个数

temp1=arm[i+1]

j=i

while j>-1 and temp1

arm[j+1]=arm[j]

ard[j+1]=ard[j]

j-=1

arm[j+1]=temp1

ard[j+1]=temp

print

print "每一个元素的最小编码为:",

zhuanhuan(arm,0,Node(arm[1],None,None))//把排序好的东西放入构建霍夫曼树

show(root)//递归输出霍夫曼编码

#生命本没有意义,我们的存在就是赋予它意义

总结

以上是生活随笔为你收集整理的python哈夫曼树_python霍夫曼树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。