數(shù)據(jù)結(jié)構(gòu)課件在一般的書中樹那章后面著者都會(huì)介紹一下

樹在一般的數(shù)據(jù)結(jié)構(gòu)的書中，樹的那章后面，著者一般都會(huì)介紹一下(HUFFMAN)樹和編碼。編碼是樹的一個(gè)應(yīng)用。編碼應(yīng)用廣泛，如JPEG中就應(yīng)用了編碼。首先介紹什么是樹。樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹。所謂樹的帶權(quán)路徑長(zhǎng)度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹的帶權(quán)路徑長(zhǎng)度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,...n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i(i=1,2,...n)。可以證明樹的WPL是最小的。在上世紀(jì)五十年代初就提出這種編碼時(shí)，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長(zhǎng)度最短的編碼。它是一種變長(zhǎng)的編碼。在編碼中，若各碼字長(zhǎng)度嚴(yán)格按照碼字所對(duì)應(yīng)符號(hào)出現(xiàn)概率的大小的逆序排列，則編碼的平均長(zhǎng)度是最小的。（注：碼字即為符號(hào)經(jīng)編碼后得到的編碼，其長(zhǎng)度是因符號(hào)出現(xiàn)的概率而不同，所以說編碼是變長(zhǎng)的編碼。）然而怎樣構(gòu)造一棵樹呢？最具有一般規(guī)律的構(gòu)造方法就是算法。一般的數(shù)據(jù)結(jié)構(gòu)的書中都可以找到其描述：一、對(duì)給定的n個(gè)權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹的初始集合={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右均為空。（為方便在計(jì)算機(jī)上實(shí)現(xiàn)算法，一般還要求以Ti的權(quán)值Wi的升序排列。）二、在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右的根結(jié)點(diǎn)的權(quán)值之和。F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合中。四、重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。C語言實(shí)現(xiàn)上述算法，可用靜態(tài)的二叉樹或動(dòng)態(tài)的二叉樹。若用動(dòng)態(tài)的二叉樹可用以下數(shù)據(jù)結(jié)構(gòu)：structtree{floatweight;/*權(quán)值*/charleaf;/*葉結(jié)點(diǎn)信息字符*/structtree*left;/*樹的左結(jié)點(diǎn)*/structtree*right;/*樹的右結(jié)點(diǎn) {/*F集合，以鏈表形式表示*/structtree*ti;/*F中的樹*/ *next;/*下一個(gè)結(jié)點(diǎn)例：若字母A，B，Z，C出現(xiàn)的概率為：0.75,0.54,0.28,0.43；則相應(yīng)的權(quán)值為：75，54，28，43。構(gòu)造好樹后，就可根據(jù)樹進(jìn)行編碼。例如：上面的字符根據(jù)其出現(xiàn)的概率作為權(quán)值構(gòu)造一棵樹后，經(jīng)編碼得到的對(duì)應(yīng)的碼值。只要使用同一棵樹，就可把編碼還原成原來那組字符。顯然編碼是前綴編碼，即任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴，否則，編碼就不能進(jìn)行a,b,c,d0，10，101，111010就可翻譯為bb或ca，因?yàn)閎的編碼是c的編碼的前綴。剛才進(jìn)行編碼的規(guī)則是從根結(jié)點(diǎn)到葉結(jié)點(diǎn)（包含原信息）的路徑，向左孩子前進(jìn)編碼為0，向右孩子前進(jìn)編碼為1，當(dāng)然你也可以反過來規(guī)定。這種編碼方法是靜態(tài)的編碼，它對(duì)需要編碼的數(shù)據(jù)進(jìn)行兩遍掃描：第一遍統(tǒng)計(jì)原數(shù)據(jù)中各字符出現(xiàn)的頻率，利用得到的頻率值創(chuàng)建樹，并必須把樹的信息保存起來，即把字符0-255(2^8=256)的頻率值以2-4BYTES的長(zhǎng)度順序起來，（用4Bytes的長(zhǎng)度頻率值，頻率值的表示范圍為0--2^32-1，這已足夠表示大文件中字符出現(xiàn)的頻率了）以便解壓時(shí)創(chuàng)建同樣的樹進(jìn)行解壓；第二遍則根據(jù)第一遍掃描得到的樹進(jìn)行編碼，并把編碼后得到的碼字起來。靜態(tài)編碼方法有一些缺點(diǎn)：一、對(duì)于過短的文件進(jìn)行編碼的意義不大，因?yàn)楣庖?BYTES的長(zhǎng)度 樹的信息就需1024Bytes的空間；二、進(jìn)行哈夫曼編碼，編碼信息時(shí)，若用與通訊網(wǎng)絡(luò)，就會(huì)引起較大的延時(shí)；三、對(duì)較大的文件進(jìn)行編碼時(shí)，頻繁的磁盤讀寫會(huì)降低數(shù)據(jù)編碼的速度。因此，后來有人提出了一種動(dòng)態(tài)的編碼方法。動(dòng)態(tài)編碼使用一棵動(dòng)態(tài)變化的樹，對(duì)第t+1個(gè)字符的編碼是根據(jù)原始數(shù)據(jù)中前t個(gè)字符得到的哈夫曼樹來進(jìn)行的，編碼和使用相同的初始樹，每處理完一個(gè)字符，編碼和使用相同的方法修改樹，所以沒有必要為而保存樹的信息。編碼和一個(gè)字符所需的時(shí)間與該字符的編碼長(zhǎng)度成正比，所以動(dòng)態(tài)編碼可實(shí)時(shí)進(jìn)行。動(dòng)態(tài)編碼比靜態(tài)編碼復(fù)雜的多，有的讀者可參考有關(guān)數(shù)據(jù)結(jié)構(gòu)與算法的書籍。前面提到的JPEG中用到了編碼，并不是說JPEG就只用編碼就可以了，而是一幅經(jīng)過多個(gè)步驟后得到它的一列數(shù)值，對(duì)這些數(shù)值進(jìn)行編碼，以便或傳輸。編碼方法比較易懂，大家可以根據(jù)它的編碼方法，自己編寫編碼和的程序。#defineMAXVALUE #define /*最大的編碼位數(shù)#defineMAXNODE30 structhaffnode{chardata;intweight;intintparent; intleftchild; int struct{intint /*編碼的起始下標(biāo)charint /*字符權(quán)值voidpprintf(structhaffcodehaffcode[],intn);voidhaffmantree(intweight[],intn,structhaffnodehafftree[],charvoidhaffmancode(structhaffnodehafftree[],intn,structhaffcodevoidtest(structhaffcodehaffcode[],intvoidend();voidhaffmantree(intweight[],intn,structhaffnodehafftree[],char{int/*樹hafftree[]初始化，n個(gè)葉結(jié)點(diǎn)共有2n-1個(gè)結(jié)點(diǎn)*/ } } } /*構(gòu)造樹n-1個(gè)非葉結(jié)點(diǎn)}else}}}}voidhaffmancode(structhaffnodehafftree[],intn,structhaffcode{/*由n個(gè)結(jié)點(diǎn)的樹hafftree[]構(gòu)成的編碼haffcode[]*/inti,j,child,parent;structhaffcodenewcode;structhaffcode*cd; /*求n個(gè)結(jié)點(diǎn)的編{cd->start=MAXBIT- /*不等長(zhǎng)編碼的 /*

/*1*/} }}voidpprintf(structhaffcodemyhaffcode[],int{inti,j,count=0; }}voidtest(structhaffcodehaffcode[],int{intcharstructhaffcodenewhaffcode[MAXNODE];cprintf("請(qǐng)輸入編碼測(cè)試數(shù)據(jù)，在此建議為'thisprogrammeismycprintf("注意小寫,T27.\n");{printf("youinputthedatanumber>=MAXNODE.");}{{{printf("在系統(tǒng)中找不到與第個(gè)%d字符相匹配的編碼\n",i+1);}}}void{intdriver,mode;initgraph(&driver,&mode,"");outtext("ThisprogrammeisdesignedbyDouZheren");outtext("thankyouusethisprogramme.");outtext("pleasepressanykeytoendthis}void{intintdriver=VGA,mode=VGAHI;charch;intweight[27]={186,64,13,22,32,103,21,15,47,charstructhaffnodenewhaffnode[2*MAXNODE-1];structhaffcodenewcode[MAXNODE];structhaffnode*myhafftree=newhaffnode;structhaffcode*myhaffcode=newcode;{printf("youinputthehaffnode>MAXNODE,soyouinputthedataiswrong");}

碼。}

cprintf("cprintf("注意：本程序只支持小寫字母，空格用大寫字母T代替! cprintf("Ready?Enter,ifyouwanttobegin!\n");printf("y繼續(xù)。否則程序?qū)⒔Y(jié)束.");usingnamespacestd;typedefcharelemtype;typedefstructtree//{elemtypeinfo;intcount;typedefstructinside_treenode//{intfather;intintbooltypedefstructtree_leaves//{charcode;intisleft;inttypedefstructlinknode//{charintfrequent;intposition;treenode*makeTree(elemtypex);//voidsetLeft(treenode*p,elemtypex);//設(shè)置左孩子voidsetRight(treenode*p,elemtypex);//設(shè)置右孩子treenode*creatTree(chara[],int&);//創(chuàng)建樹voiddisy(treenode*ptree);//以廣義表有格式輸出一棵voidinTraver(treenode*p,linknode*t,l_node*s,int);//中序扁歷slinknode*insert_slink(slinknode*t,char,int,int);//鏈表中插入結(jié)點(diǎn)voidhuffman(treenode*rootTree,intnum_of_leave,chara[]);//創(chuàng)建boolis_leaf(slinknode*t);//intset(slinknode*s,l_node*l,i_node*in);//通過排序鏈表，完成對(duì)葉子數(shù)intsq_Dichotomy_Search0(l_node*l,intn,charkey);//voidcodeToSymb(l_node*l,i_node*i,introottree,chara[]);//將二進(jìn)制位int{chara[1000];//存放將要編輯的文本intnumofleave;//葉子的個(gè)數(shù)treenode*rootTree=creatTree(a,numofleave);//通過用來設(shè)return}treenode*makeTree(elemtypex)//{treenode*p=newtreenode;returnp;}voidsetLeft(treenode*p,elemtypex)//{treenode*q=newtreenode;}voidsetRight(treenode*p,elemtypex)//{treenode*q=newtreenode;p-}treenode*creatTree(chara[],int&num_of_char)//ASCII{intelemtypex;booljudge;n{judge=false;//judge{if(x<p-{p=p-}elseif(x==p-{}{p=p-}}{}{}}returnrootTree;}staticintstatic_i=0;//靜態(tài)數(shù)據(jù)的用法，以實(shí)現(xiàn)遞歸中參數(shù)和的傳遞voidinTraver(treenode*p,slinknode*t,l_node*s,inti)//樹的中序扁歷code{inTraver(p-}}slinknode*insert_slink(slinknode*head,charcc,intf,int{t=newslinknode;t-{returnhead;}if(f<head-{}{while(p!=NULL&&f>p-{p=p-{}}return}voidhuffman(treenode*rootTree,int{l_node*leafnodes=newl_node[num_of_leave];//存放葉子結(jié)點(diǎn)linknode*headnode=newlinknode;//headnodeheadnodedeletet;if(headnode->code=='n'&&headnode-{delete}i_node*inside_nodes=newi_node[num_of_leave-1];introottree=set(headnode,leafnodes,inside_nodes);inti,ii,position,jj,j=0,posotion_of_bcode=0;charbcode[30],bcode1[2000];{position=sq_Dichotomy_Search0(leafnodes,num_of_leave,a[i]);{}{}jj=leafnodes[position].father;{{}{}}for(ii=posotion_of_bcode-2;i