哈夫曼樹的建立與操作

1、實(shí)驗(yàn)六哈夫曼樹的建立與操作一、實(shí)驗(yàn)要求和實(shí)驗(yàn)內(nèi)容1輸入哈夫曼樹葉子結(jié)點(diǎn)(信息和權(quán)值)2、由葉子結(jié)點(diǎn)生成哈夫曼樹內(nèi)部結(jié)點(diǎn)3、生成葉子結(jié)點(diǎn)的哈夫曼編碼4、顯示哈夫曼樹結(jié)點(diǎn)順序表二、 詳細(xì)代碼(內(nèi)包含了詳細(xì)的注釋)：#in cludeusing n amespace std;typedef char Elemtype;struct eleme ntint weight;Elemtype date;eleme nt* lchild,*rchild;class Huffma nTreepublic:HuffmanTree() 構(gòu)造函數(shù)cout請輸入二叉樹的個(gè)數(shù) co unt;element *s=new

2、 elementcount;/s為指向數(shù)組的指針，保存指向數(shù)組的地址 for(i nt i=0;ico un t;i+)cout輸入第i+1個(gè)節(jié)點(diǎn)的權(quán)值 si.weight;cout輸入第i+1個(gè)節(jié)點(diǎn)的內(nèi)容 si.date;sichild=NULL;si.rchild=NULL;/以上為初始化每一個(gè)結(jié)點(diǎn)eleme nt * *m=n ew eleme nt*cou nt;/m為指向數(shù)組成員的地址的指針，保存【指向數(shù)組成員地址的指針】的地址for(i nt i=0;ico un t;i+)mi=s+i;把數(shù)組成員i地址賦給mi ( mi大致意思等效于*m)以下為哈夫曼的構(gòu)造過程eleme nt*

3、q;for(i nt i=0;ico un t-1;i+)int a=32767,b=32767;/a,b為兩個(gè)存當(dāng)前最小值的兩個(gè)臨時(shí)變量，初始化為 32767( int型能達(dá)到的最大的值)for(i nt i=1;iweightweight;return仁i;for(i nt i=0;iweightweighta)b=mi-weight;return2=i;q=new eleme nt;構(gòu)建一棵新樹q-weight=mreturn1-weight+mreturn2-weight;q-lchild=mretur n1;q-rchild=mreturn2;mreturn1=q;mreturn2=

4、NULL;/用新樹替換原來的兩子樹，并置空一個(gè)數(shù)boot=q;/把最后取得的哈夫曼樹的頭結(jié)點(diǎn)即q賦值給bootcout哈夫曼樹構(gòu)造成功lchild&!bt-rchild)當(dāng)此結(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)進(jìn)入cout權(quán)值為date結(jié)點(diǎn)的哈夫曼編碼為：;for(i nt i=0;ile n; i+)coutmi;coutlchild,le n+1);mle n=1; Hufuma nCodi ng(bt-rchild,le n+1);eleme nt* ReturnBoot()return boot;private:int count;/ 結(jié)點(diǎn)數(shù)int return1,return2;權(quán)值最小的節(jié)點(diǎn)的在數(shù)組中的位置eleme nt* boot;int m20;/存儲(chǔ)哈夫曼編碼;int mai n()eleme nt* m;Huffma nTree a;m=a.ReturnBoot();a.Hufuma nCodi ng(m);三、運(yùn)行結(jié)果QBC:WI N DOWSsystem 3 2c md.exe為為為為3 馬 ripriprim I-串帀帀帀5 二冊” n冊.-n冊IJ冊 &. 曼曼曼曼晏- r瞻璧 .蜚點(diǎn)占苦 忡士 口士口吉吉士口歿 %$d&壽矗章 為為為為韋16901SB11B1育輸人二叉樹的個(gè)數(shù) 矗心丄個(gè)節(jié)點(diǎn)的杈值 書入第丄個(gè)節(jié)點(diǎn)的內(nèi)容 仞入第去個(gè)節(jié)點(diǎn)