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霍夫曼树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。