哈夫曼樹需要實現的演算法

A. 哈夫曼樹演算法

題目的闡述：以N進制編碼方式對一個英文字串中的字元進行編碼，每個不同的字元其編碼不同．使得由新的編碼替代原串後總碼長最小，且輸入0，1，2，．．．，N－1構成的數字串後，依照該編碼方式可以正確的對譯出唯一的英文原串．如：N＝3英文原串為ABBCBADDACE其對應的一種編碼方式為A：00B：01C：020D：021E：022原串對譯後的編碼為000101020010002102100020022其碼長為27若輸入編碼串0102002200則對應的英文原串為BCEA 分析： 假設英文原串中的字元存放於字元集S中，‖S‖＝X，每個字元在字串中出現的概率為W［i］，L［i］為字元i的編碼長．依題意得，對S集合中的不同字元進行N進制編碼後要求1）新字串的碼長最短WPL＝∑W［i］＊L［i］
（i∈1．．X）使得在WPL是所有編碼方式中的最小值2）編碼無二義性任意一字元編碼都不為其它字元編碼的前綴 此題以哈夫曼樹來解答是非常適宜的．N為此哈夫曼樹的分叉數，S字元集里的元素即為此N叉哈夫曼樹的葉子，概率W［i］即為葉子結點的權重，從根結點到各葉子結點的路徑長即為該葉子結點的編碼長L［i］．由哈夫曼樹的思想可以知道哈夫曼樹的建立是一步到位的貪心法，即權重越大的結點越靠近該樹的根，這樣，出現頻率越大的字元其編碼就越短．但具體應該怎樣建立起此N叉哈夫曼樹呢？我們首先以N＝2為例：S＝｛A，B，C，D｝W＝［3，1，2，1］首先從W中選出兩個最小權，1，1，將其刪去，並以2（即1＋1）替代W＝［3，2，2］；再從新的W中取出兩個最小權，2，2，將其刪去，並以4（即2＋2）替代W＝［3，4］；依此類推，直到W中只一個值時合並結束，此時W＝［7］以上兩兩合並的過程即為二叉哈夫曼樹的建立過程，每一次的合並即是將兩棵子樹歸於一個根結點下，於是可以建立二叉樹如下： m0åæ1mmA0åæ1mmC0åæ1mmBD MIN－WPL＝3＊1＋1＊3＋2＊2＋1＊3＝13 從某一根結點出發走向其左子樹標記為0，走向其右子樹標記為1，則可以得到以下編碼A，B，C，D對應的編碼為A：0B：110C：10D：111
N＝3時又是怎樣一種情況呢？設S＝｛A，B，C，D，E｝W＝［7，4，2，5，3｝則按權重排序可得S＝｛D，B，E，C，A｝W＝［7，5，4，3，2］那麼此哈夫曼樹的樹形應為怎樣呢？是以下的左圖，還是右圖，或是兩者均不是mmåâæåæmmllmåæåæCAåælllllmADBEDåæ
lmBåællEC 顯然，要帶權路徑長WPL最短，那麼，此樹的高度就應盡可能的小，由此可知將此樹建成豐滿N叉樹是最合理的，於是我們盡量使樹每一層都為N個分枝．對於這道題的情況，我們具體來分析．按照哈夫曼樹的思想，首先從W中取出權最小的三個值，即2，3，4，並以9（2＋3＋4）來代替，得到新的W＝［9，7，5］；再將這三個值合並成9＋7＋5＝21這個結點．於是得到三叉哈夫曼樹如下：måâællmDBåâælllECAWPL＝1＊7＋1＊5＋2＊2＋2＊3＋2＊4＝30以0．．N－1依次標記每個根結點的N個分枝，則可以得到每個字元相對應的編碼：A：22B：1C：21D：0E：20我們發現對於這種情況恰巧每層均為N個分枝，但事實上並非所有的N叉哈夫曼樹都可得到每層N個分枝．例於當N＝3，‖S‖＝6時就不可能構成一棵每層都為三個分枝的三叉樹．如何來處理這種情況呢？最簡單的處理方式就是添加若干出現概率為0的空字元填補在N叉樹的最下一層，這些權為0的虛結點並無實際意義但卻非常方全便於這棵N叉樹的建立．空字元的添加個數add的計算如下：Y＝‖S‖mod（n－1）add＝0（Y＝1）add＝1（Y＝0）add＝N－Y（Y＞1） 虛結點的加入使得權重最小的N－add個字元構成了距根結點最遠的分枝，使其它字元構成的N叉樹保持了豐滿的N叉結構．例：N＝3S＝｛A，B，C，D，E，F｝W＝［1，2，3，4，5，6｝則y：＝6mod（3－1）＝0add＝1於是構成N叉樹如下：­為虛結點¡åâællmFEåâællmDCåâæBA­WPL＝1＊6＋1＊5＋2＊4＋2＊3＋3＊2＋3＊1＋3＊0＝33對應編碼為：A：221B：220C：21D：20E：1F：0

B. 哈夫曼的如何構造

然而怎樣構造一棵哈夫曼樹呢？最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述： 重復二和三兩步，直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法，可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構： struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合，以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例：若字母A，B，C，D出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，110，111，對於編碼串：1010就翻譯為bb。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規定。

C. 請描述哈夫曼演算法，並用圖描述構造哈夫曼樹的過程。

這個講的相當清楚。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
哈夫曼在上世紀五十年代初就提出這種編碼時，根據字元出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。（註：碼字即為符號經哈夫曼編碼後得到的編碼，其長度是因符號出現的概率而不同，所以說哈夫曼編碼是變長的編碼。）
然而怎樣構造一棵哈夫曼樹呢？最具有一般規律的構造方法就是哈夫曼演算法。一般的數據結構的書中都可以找到其描述：
一、對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。（為方便在計算機上實現演算法，一般還要求以Ti的權值Wi的升序排列。）
二、在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。
三、從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。
四、重復二和三兩步，直到集合F中只有一棵二叉樹為止。
用C語言實現上述演算法，可用靜態的二叉樹或動態的二叉樹。若用動態的二叉樹可用以下數據結構： struct tree{
float weight; /*權值*/
union{
char leaf; /*葉結點信息字元*/
struct tree *left; /*樹的左結點*/
};
struct tree *right; /*樹的右結點*/
};
struct forest{ /*F集合，以鏈表形式表示*/
struct tree *ti; /* F中的樹*/
struct forest *next; /* 下一個結點*/
};
例：若字母A，B，Z，C出現的概率為：0.75,0.54,0.28,0.43；則相應的權值為：75，54，28，43。
構造好哈夫曼樹後，就可根據哈夫曼樹進行編碼。例如：上面的字元根據其出現的概率作為權值構造一棵哈夫曼樹後，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字元。顯然哈夫曼編碼是前綴編碼，即任一個字元的編碼都不是另一個字元的編碼的前綴，否則，編碼就不能進行翻譯。例如：a,b,c,d的編碼為：0，10，101，11，對於編碼串：1010就可翻譯為bb或ca，因為b的編碼是c的編碼的前綴。剛才進行哈夫曼編碼的規則是從根結點到葉結點（包含原信息）的路徑，向左孩子前進編碼為0，向右孩子前進編碼為1，當然你也可以反過來規定。
這種編碼方法是靜態的哈夫曼編碼，它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。 靜態哈夫曼編碼方法有一些缺點：一、對於過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；二、進行哈夫曼編碼，存儲編碼信息時，若用與通訊網路，就會引起較大的延時；三、對較大的文件進行編碼時，頻繁的磁碟讀寫訪問會降低數據編碼的速度。
因此，後來有人提出了一種動態的哈夫曼編碼方法。動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。動態哈夫曼編碼比靜態哈夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與演算法的書籍。
前面提到的JPEG中用到了哈夫曼編碼，並不是說JPEG就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。

D. 試編寫實現哈夫曼樹和哈夫曼編碼的演算法這是數據結構里的問題，要求用C++6.0來實現

#include <stdio.h>
#include <malloc.h>
#include<math.h>
struct hf
{
char data;
int weight;
struct hf *lc;
struct hf *rc;
struct hf *pc;
int hcd[30];
} *hc[30];
int n;

main()
{struct hf creat();
struct hf bian(struct hf *hc[30]);
struct hf print(struct hf *hc[30]);
int m;
do
{
printf("親!請輸入你所需要的功能：\n1代表構建哈夫曼樹，2代表給哈夫曼樹賦權值，3代表輸出哈夫曼樹的權值");
scanf("%d",&m);
switch(m)
{
case 1:creat();break;
case 2:bian(hc);break;
case 3:print(hc);break;

}
}while (m==1||m==2||m==3);

}

struct hf creat()
{
int i,m,k,p,t,r,u;
int selete (int k,struct hf *hc[30]);
printf("請輸入你所需要構建哈夫曼樹的個數:");
scanf("%d",&n);

for(i=0;i<n;i++)
{
getchar();
printf("請輸入數據的符號");
hc[i]= (struct hf *)malloc(sizeof(struct hf));
scanf("%c",&hc[i]->data);
printf("請輸入數據的權值：");
scanf("%d",&hc[i]->weight);
hc[i]->lc=0;
hc[i]->rc=0;
}
for(t=n;t<(2*n-1);t++)
{
hc[t]=(struct hf *)malloc(sizeof(struct hf));

}
for(u=0;u<(2*n-1);u++)
{
hc[u]->pc=0;
}

for(m=n;m<((2*n)-1);m++)
{ hc[m]->weight=0;
for(r=1;r<=2;r++)
{
p=selete(m,hc);
if(r==1)

{hc[m]->lc=hc[p];
hc[p]->pc=hc[m];

}
if(r==2)
{
hc[m]->rc=hc[p];
hc[p]->pc=hc[m];

}
hc[m]->weight=hc[m]->weight+hc[p]->weight;
}
}
}

int selete(int k,struct hf *hc[30])
{ int a,i,j;

for (i=0;i<k;)
{

if(hc[i]->pc!=0)

i++;

else
{
a=i;
for(j=i+1;j<k;)
{
if(hc[j]->pc!=0)
j++;
else if(hc[a]->weight>hc[j]->weight)
{
a=j;
j++;
}else j++;
}return (a);

}
}

}

struct hf bian(struct hf *hc[30])
{int i,m,t;
struct hf *p1,*p2;
for(i=0;i<n;i++)
{m=0;p1=hc[i];
while(p1->pc!=0)

{ p2=p1->pc;

if(p2->lc==p1)
{hc[i]->hcd[m]=0;
m++;
p1=p1->pc;
}
if(p2->rc==p1)
{ hc[i]->hcd[m]=1;
m++;
p1=p1->pc;
}

}
hc[i]->hcd[29]=m;
}

}

struct hf print(struct hf *hc[30])
{int i,p,m;

printf("其編碼結果如下：\n");
for (i=0;i<n;i++)
{m=hc[i]->hcd[29];
for(p=m-1;p>=0;p--)
{printf("******* %c的哈夫曼編碼為*******\n",hc[i]->data);
for(p=m-1;p>=0;p--)
printf(" %d ",hc[i]->hcd[p]);
printf("\n");
}
}

}

E. 數據結構的問題,求一個構造哈夫曼樹的演算法

void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
/*建立葉結點個數為n，權值數組為weight[]的哈夫曼樹*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼樹hafftree[]初始化，n個葉結點共有2n-1個結點*/
for(i=0;i<2*n-1;i++)
{if(i<n) {hafftree[i].data=data[i];
hafftree[i].weight=weight[i]; /*葉結點*/
}
else {hafftree[i].weight=0; /*非葉結點*/
hafftree[i].data='\0';
}
hafftree[i].parent=0; /*初始化沒有雙親結點*/
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++) /*構造哈夫曼樹n-1個非葉結點*/
{m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{if(hafftree[j].weight<m1&&hafftree[j].flag==0)
{m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
{m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;

}
}
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[])
{/*由n個結點的哈夫曼樹hafftree[]構成的哈夫曼編碼haffcode[]*/
int i,j,child,parent;
struct haffcode newcode;
struct haffcode *cd;
cd=&newcode;
for(i=0;i<n;i++) /*求n個結點的哈夫曼編碼*/
{cd->start=MAXBIT-1; /*不等長編碼的最後一位是n-1*/
cd->weight=hafftree[i].weight;
cd->data=hafftree[i].data; /*取得編碼對應值的字元*/
child=i;
parent=hafftree[child].parent;
while(parent!=0)
{if(hafftree[parent].leftchild==child)
cd->bit[cd->start]=0; /*左孩子編碼為0*/
else
cd->bit[cd->start]=1; /*右孩子編碼為1*/
cd->start--;
child=parent;
parent=hafftree[child].parent;
}
for(j=cd->start+1;j<MAXBIT;j++) /*保存每個葉結點的編碼和等長編碼的起始位*/
haffcode[i].bit[j]=cd->bit[j];
haffcode[i].data=cd->data;
haffcode[i].start=cd->start;
haffcode[i].weight=cd->weight;
}
}

F. 哈夫曼樹及哈夫曼編碼的C程序實現(數據結構題)

去年做的課程設計，有什麼不合要求的自己改改

#include<string.h>
#include<stdlib.h>
#include<stdio.h>

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 演算法6.13
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼樹的構造過程如下所示：");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2。
Select(HT, i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
}

//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父結點，編碼長度減1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("輸入結點數:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各結點的哈夫曼編碼:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}

G. 哈夫曼演算法

計算過程如圖所示：

H. 哈夫曼樹的構造演算法

/*-------------------------------------------------------------------------
*Name:哈夫曼編碼源代碼。
*Date:2011.04.16
*Author:JeffreyHill+Jezze(解碼部分)
*在Win-TC下測試通過
*實現過程：著先通過HuffmanTree()函數構造哈夫曼樹，然後在主函數main()中
*自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷，若在
*父結點左側，則置碼為0,若在右側,則置碼為1。最後輸出生成的編碼。
*------------------------------------------------------------------------*/
#include<stdio.h>
#include<stdlib.h>

#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1

typedefstruct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*編碼結構體*/
typedefstruct
{
intweight;
intparent;
intlchild;
intrchild;
intvalue;
}HNodeType;/*結點結構體*/

/*構造一顆哈夫曼樹*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn)
{
/*i、j：循環變數，m1、m2：構造哈夫曼樹不同過程中兩個最小權值結點的權值，
x1、x2：構造哈夫曼樹不同過程中兩個最小權值結點在數組中的序號。*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼樹數組HuffNode[]中的結點*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;//權值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//實際值，可根據情況替換為字母
}/*endfor*/

/*輸入n個葉子結點的權值*/
for(i=0;i<n;i++)
{
printf("Pleaseinputweightofleafnode%d:
",i);
scanf("%d",&HuffNode[i].weight);
}/*endfor*/

/*循環構造Huffman樹*/
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;/*m1、m2中存放兩個無父結點且結點權值最小的兩個結點*/
x1=x2=0;
/*找出所有結點中權值最小、無父結點的兩個結點，並合並之為一顆二叉樹*/
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*設置找到的兩個子結點x1、x2的父結點信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;

printf("x1.weightandx2.weightinround%d:%d,%d
",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用於測試*/
printf("
");
}/*endfor*/
/*for(i=0;i<n+2;i++)
{
printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///測試
}/*endHuffmanTree*/

//解碼
voiddecodeing(charstring[],HNodeTypeBuf[],intNum)
{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];

while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{

if(*nump==0)
{
tmp=Buf[tmp].lchild;
}
elsetmp=Buf[tmp].rchild;
nump++;

}

printf("%d",Buf[tmp].value);
}


}


intmain(void)
{

HNodeTypeHuffNode[MAXNODE];/*定義一個結點結構體數組*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定義一個編碼結構體數組，同時定義一個臨時變數來存放求解編碼時的信息*/
inti,j,c,p,n;
charpp[100];
printf("Pleaseinputn:
");
scanf("%d",&n);
HuffmanTree(HuffNode,n);


for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)/*父結點存在*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求編碼的低一位*/
c=p;
p=HuffNode[c].parent;/*設置下一循環條件*/
}/*endwhile*/

/*保存求出的每個葉結點的哈夫曼編碼和編碼的起始位*/
for(j=cd.start+1;j<n;j++)
{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/

/*輸出已保存好的所有存在編碼的哈夫曼編碼*/
for(i=0;i<n;i++)
{
printf("%d'sHuffmancodeis:",i);
for(j=HuffCode[i].start+1;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("start:%d",HuffCode[i].start);

printf("
");

}
/*for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("
");
}*/
printf("Decoding?PleaseEntercode:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return0;
}

http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html

I. 數據結構哈夫曼樹的演算法

每次取最小的2個合並後的值繼續加入集合進行比較，直到集合里只有一個數為止，這樣就可以達到權值最小的路徑越長，權值越大的路徑越短，即可以找到最小權值路徑