第利用Python和C語言分別實(shí)現(xiàn)哈夫曼編碼temp=root.rchild;//后訪問右孩子

while(temp==NULL)//右孩子為空，代表左右孩子均已訪問，結(jié)點(diǎn)可以出棧

//結(jié)點(diǎn)出棧

root=pop(bs);

//尋到葉子結(jié)點(diǎn)，可以得到結(jié)點(diǎn)中字符的編碼

if(root.c!='')

traverseStack(cs,root.c);

charPop(cs);//字符棧出棧

if(bs.top==bs.base)break;//根結(jié)點(diǎn)出棧，遍歷結(jié)束

//查看上一級(jí)結(jié)點(diǎn)是否訪問完左右孩子

root=getTop(bs);

temp=root.rchild;

if(bs.top!=bs.base)

//將結(jié)點(diǎn)右孩子設(shè)為空，代表已訪問其右孩子

root.rchild=NULL;

pop(bs);

push(bs,root);

//右孩子入棧

root=*temp;

push(bs,root);

//'1'入字符棧

charPush(cs,'1');

e解碼：

'''C

chardecode[100];//記錄解碼得到的字符串

//通過哈夫曼樹解碼

voiddecodeHuffman(TreeT,char*code)

intcnt=0;

Treeroot;

while(*code!='\0')//01編碼字符串讀完，解碼結(jié)束

root=T;

while(root-lchild!=NULL)//找到葉子結(jié)點(diǎn)

if(*code!='\0')

if(*code=='0')

root=root-lchild;

else

root=root-rchild;

code++;

elsebreak;

decode[cnt]=root-//葉子結(jié)點(diǎn)存放的字符即為解碼得到的字符

cnt++;

f主函數(shù)：

'''C

voidmain()

pListpl=creatList();

printf("字符的權(quán)重如下\n");

for(pListl=pl;l-next!=NULL;l=l-next)

printf("字符%c的權(quán)重是%d\n",l-root-c,l-root-weight);

TreeT=creatHuffman(pl);

encodeHuffman(T);

printf("\n\n字符編碼結(jié)果如下\n");

for(inti=0;ii++)

printf("%c:%s\n",i+'a',stack[i]);

charcode[100];

printf("\n\n請(qǐng)輸入編碼：\n");

scanf("%s",code);

printf("解碼結(jié)果如下：\n");

decodeHuffman(T,code);

printf("%s\n",decode);

printf("\n\n");

system("date/T");

system("TIME/T");

system("pause");

exit(0);

1.2運(yùn)行結(jié)果

2.Python實(shí)現(xiàn)

2.1代碼說明

a創(chuàng)建哈夫曼樹：

#coding=gbk

importdatetime

importtime

frompip._patimportraw_input

#哈夫曼樹結(jié)點(diǎn)類

classHuffman:

def__init__(self,c,weight):

self.c=c

self.weight=weight

self.lchild=None

self.rchild=None

#創(chuàng)建結(jié)點(diǎn)左右孩子

defcreat(self,lchild,rchild):

self.lchild=lchild

self.rchild=rchild

#創(chuàng)建列表

defcreatList():

list=[]

list.append(Huffman('a',22))

list.append(Huffman('b',5))

list.append(Huffman('c',38))

list.append(Huffman('d',9))

list.append(Huffman('e',44))

list.append(Huffman('f',12))

list.append(Huffman('g',65))

returnlist

#通過列表創(chuàng)建哈夫曼樹，返回樹的根結(jié)點(diǎn)

defcreatHuffman(list):

whilelen(list)1:#列表只剩一個(gè)結(jié)點(diǎn)時(shí)循環(huán)結(jié)束，此結(jié)點(diǎn)即為哈夫曼樹的根結(jié)點(diǎn)

i=0

j=1

k=2

whileklen(list):#找到列表中權(quán)重最小的兩個(gè)結(jié)點(diǎn)list1,list2

iflist[i].weightlist[k].weightorlist[j].weightlist[k].weight:

iflist[i].weightlist[j].weight:

i=k

else:

j=k

k+=1

root=Huffman('',list[i].weight+list[j].weight)#新結(jié)點(diǎn)字符統(tǒng)一設(shè)為空格，權(quán)重設(shè)為list1與list2權(quán)重之和

iflist[i].weightlist[j].weight:#list1和list2設(shè)為新結(jié)點(diǎn)的左右孩子

root.creat(list[i],list[j])

else:

root.creat(list[j],list[i])

#list1數(shù)據(jù)域替換成新結(jié)點(diǎn)，并刪除list2

list[i]=root

list.remove(list[j])

returnlist[0]

b編碼：

#通過哈夫曼樹編碼

defencodeHuffman(T):

code=[[],[],[],[],[],[],[]]

#列表實(shí)現(xiàn)棧結(jié)構(gòu)

treeStack=[]

codeStack=[]

treeStack.append(T)

whiletreeStack!=[]:#?？沾肀闅v結(jié)束

root=treeStack[-1]

temp=root.lchild

whiletemp!=None:

#將結(jié)點(diǎn)左孩子設(shè)為空，代表已訪問其左孩子

root.lchild=None

#左孩子入棧

treeStack.append(temp)

root=temp

temp=root.lchild

#0入編碼棧

codeStack.append(0)

temp=root.rchild#后訪問右孩子

whiletemp==None:#右孩子為空，代表左右孩子均已訪問，結(jié)點(diǎn)可以出棧

root=treeStack.pop()#結(jié)點(diǎn)出棧

#尋到葉子結(jié)點(diǎn)，可以得到結(jié)點(diǎn)中字符的編碼

ifroot.c!='':

codeTemp=codeStack.copy()

code[ord(root.c)-97]=codeTemp

iftreeStack==[]:#根結(jié)點(diǎn)出棧，遍歷結(jié)束

break

codeStack.pop()#編碼棧出棧

#查看上一級(jí)結(jié)點(diǎn)是否訪問完左右孩子

root=treeStack[-1]

temp=root.rchild

iftreeStack!=[]:

treeStack.append(temp)#右孩子入棧

root.rchild=None#將結(jié)點(diǎn)右孩子設(shè)為空，代表已訪問其右孩子

codeStack.append(1)#1入編碼棧

returncode

c解碼：

#通過哈夫曼樹解碼

defdecodeHuffman(T,strCode):

decode=[]

index=0

whileindexlen(strCode):#01編碼字符串讀完，解碼結(jié)束

root=T

whileroot.lchild!=None:#找到葉子結(jié)點(diǎn)

ifindexlen(strCode):

ifstrCode[index]=='0':

root=root.lchild

else:

root=root.rchild

index+=1

else:

break

decode.append(root.c)#葉子結(jié)點(diǎn)存放的字符即為解碼得到的字符

returndecode

d主函數(shù)：

if__name__=='__main__':

list=creatList()

print("字符的權(quán)重如下")

foriinrange(len(list)):

print("字符{}的權(quán)重為:{}".format(chr(i+97),list[i].weight))

T=creatHuffman(list)

code=encodeHuffman(T)

print("\n字符編碼結(jié)果如下")

foriinrange(len(code)):

print(chr(i+97),end=':')

forjinrange(len(code[i])):

print(code[i][j],end='')

print("")

strCode=input("\n請(qǐng)輸入編碼：\n")

#哈夫曼樹在編碼時(shí)被破壞，必須重建哈夫曼樹

list=creatList()

T=creatHuffman(list)

decode=decodeHuffman(T,strCode)

print("解碼結(jié)果如下：")

foriinrange(len(decode)):