常見哈夫曼樹演算法

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

1. 根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權wi的根結點，左右子樹均空。
2. 在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
3. 在F中刪除這兩棵樹，並將新的二叉樹加入F中。
4. 重復前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹
幫你貼過來了，網路
這東西實際用法是可以減少樹的訪問次數，因為他把頻率高的點放在比較靠近根節點的地方，頻率低的在下面，這樣訪問速度快。舉個例子，比如四個點，他們的使用頻率分別是1,2,3,4，然後構成的樹就是
4
0 3
0 2
0 1
補：打不出樹形結構...

2. 哈夫曼樹&帶權路徑計算

——即最短帶權路徑二叉樹，即最優二叉樹。將樹的節點值升序排序，由葉至根構建二叉樹，每次選兩個最小的節點連接，加法得到其父節點值。最終根節點權為0，向葉子節點依次遞增1。

eg：w={1,4,9,16,25,36,49,64,81,100}

最終哈夫曼樹：

最終帶權路徑長度：

WPL=2*100+2*81+3*64+3*36+3*49+4*25+5*16+6*9+7*1+7*4=1078

3. 哈夫曼樹演算法

題目的闡述：以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

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

這個講的相當清楚。
首先介紹什麼是哈夫曼樹。哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為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就只用哈夫曼編碼就可以了，而是一幅圖片經過多個步驟後得到它的一列數值，對這些數值進行哈夫曼編碼，以便存儲或傳輸。哈夫曼編碼方法比較易懂，大家可以根據它的編碼方法，自己編寫哈夫曼編碼和解碼的程序。

5. 哈夫曼樹解碼的演算法思路，語言描述即可

你講的是實現時的語言注釋，還是他的實現過程

6. 數據結構求赫夫曼樹的演算法

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

typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}htnode,*huffmantree;

typedef char **huffmancode;

int min1(huffmantree t,int i)
{
int j,flag;
unsigned int k=UINT_MAX; // 取k為不小於可能的值(即unsigned int類型的最大值)
for(j = 1; j <= i; j++)
if(t[j].weight < k && t[j].parent == 0)
k = t[j].weight,flag = j;
t[flag].parent=1;
return flag;
}

// s1為最小的兩個值中序號小的那個
void select(huffmantree t,int i,int *s1,int *s2)
{
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1 > *s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void huffmancoding(huffmantree *HT,huffmancode *HC,int *w,int n)
{
int m,i,s1,s2,start;
unsigned c,f;
huffmantree p;
char *cd;

if(n<=1)
return;
m=2*n-1;
*HT=(huffmantree)malloc((m+1)*sizeof(htnode));
for(p=*HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
(*p).parent=0;
for(i=n+1;i<=m;++i)
{
select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
}
*HC=(huffmancode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=(*HT)[i].parent; f!=0; c=f,f=(*HT)[f].parent)
if((*HT)[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
(*HC)[i]=(char*)malloc((n-start)*sizeof(char));

strcpy((*HC)[i],&cd[start]);
}
free(cd);
}

int main()
{
huffmantree HT;
huffmancode HC;
int *w,n,i;

printf("請輸入權值的個數(>1)：\n");
scanf("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("請依次輸入%d個權值(整型)：\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",w+i);
huffmancoding(&HT,&HC,w,n);
for(i=1;i<=n;i++)
puts(HC[i]);
return 0;
}

不知道是不是你要的

7. 哈夫曼樹演算法

題目的闡述：以Ｎ進制編碼方式對一個英文字串中的字元進行編碼，每個不同的字元其編碼不同．使得由新的編碼替代原串後總碼長最小，且輸入０，１，２，．．．，Ｎ－１構成的數字串後，依照該編碼方式可以正確的對譯出唯一的英文原串．如：Ｎ＝３英文原串為ＡＢＢＣＢＡＤＤＡＣＥ其對應的一種編碼方式為Ａ：００Ｂ：０１Ｃ：０２０Ｄ：０２１Ｅ：０２２原串對譯後的編碼為０００１０１０２００１０００２１０２１０００２００２２其碼長為２７若輸入編碼串０１０２００２２００則對應的英文原串為ＢＣＥＡ 分析： 假設英文原串中的字元存放於字元集Ｓ中，‖Ｓ‖＝Ｘ，每個字元在字串中出現的概率為Ｗ［ｉ］，Ｌ［ｉ］為字元ｉ的編碼長．依題意得，對Ｓ集合中的不同字元進行Ｎ進制編碼後要求１）新字串的碼長最短ＷＰＬ＝∑Ｗ［ｉ］＊Ｌ［ｉ］ （ｉ∈１．．Ｘ）使得在ＷＰＬ是所有編碼方式中的最小值２）編碼無二義性任意一字元編碼都不為其它字元編碼的前綴 此題以哈夫曼樹來解答是非常適宜的．Ｎ為此哈夫曼樹的分叉數，Ｓ字元集里的元素即為此Ｎ叉哈夫曼樹的葉子，概率Ｗ［ｉ］即為葉子結點的權重，從根結點到各葉子結點的路徑長即為該葉子結點的編碼長Ｌ［ｉ］．由哈夫曼樹的思想可以知道哈夫曼樹的建立是一步到位的貪心法，即權重越大的結點越靠近該樹的根，這樣，出現頻率越大的字元其編碼就越短．但具體應該怎樣建立起此Ｎ叉哈夫曼樹呢？我們首先以Ｎ＝２為例：Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ｝Ｗ＝［３，１，２，１］首先從Ｗ中選出兩個最小權，１，１，將其刪去，並以２（即１＋１）替代Ｗ＝［３，２，２］；再從新的Ｗ中取出兩個最小權，２，２，將其刪去，並以４（即２＋２）替代Ｗ＝［３，４］；依此類推，直到Ｗ中只一個值時合並結束，此時Ｗ＝［７］以上兩兩合並的過程即為二叉哈夫曼樹的建立過程，每一次的合並即是將兩棵子樹歸於一個根結點下，於是可以建立二叉樹如下： m０�0�2�0�3１mmＡ０�0�2�0�3１mmＣ０�0�2�0�3１mmＢＤ ＭＩＮ－ＷＰＬ＝３＊１＋１＊３＋２＊２＋１＊３＝１３ 從某一根結點出發走向其左子樹標記為０，走向其右子樹標記為１，則可以得到以下編碼Ａ，Ｂ，Ｃ，Ｄ對應的編碼為Ａ：０Ｂ：１１０Ｃ：１０Ｄ：１１１ Ｎ＝３時又是怎樣一種情況呢？設Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝Ｗ＝［７，４，２，５，３｝則按權重排序可得Ｓ＝｛Ｄ，Ｂ，Ｅ，Ｃ，Ａ｝Ｗ＝［７，５，４，３，２］那麼此哈夫曼樹的樹形應為怎樣呢？是以下的左圖，還是右圖，或是兩者均不是mm�0�2�0�9�0�3�0�2�0�3mmllm�0�2�0�3�0�2�0�3ＣＡ�0�2�0�3lllllmＡＤＢＥＤ�0�2�0�3 lmＢ�0�2�0�3llＥＣ 顯然，要帶權路徑長ＷＰＬ最短，那麼，此樹的高度就應盡可能的小，由此可知將此樹建成豐滿Ｎ叉樹是最合理的，於是我們盡量使樹每一層都為Ｎ個分枝．對於這道題的情況，我們具體來分析．按照哈夫曼樹的思想，首先從Ｗ中取出權最小的三個值，即２，３，４，並以９（２＋３＋４）來代替，得到新的Ｗ＝［９，７，５］；再將這三個值合並成９＋７＋５＝２１這個結點．於是得到三叉哈夫曼樹如下：m�0�2�0�9�0�3llmＤＢ�0�2�0�9�0�3lllＥＣＡＷＰＬ＝１＊７＋１＊５＋２＊２＋２＊３＋２＊４＝３０以０．．Ｎ－１依次標記每個根結點的Ｎ個分枝，則可以得到每個字元相對應的編碼：Ａ：２２Ｂ：１Ｃ：２１Ｄ：０Ｅ：２０我們發現對於這種情況恰巧每層均為Ｎ個分枝，但事實上並非所有的Ｎ叉哈夫曼樹都可得到每層Ｎ個分枝．例於當Ｎ＝３，‖Ｓ‖＝６時就不可能構成一棵每層都為三個分枝的三叉樹．如何來處理這種情況呢？最簡單的處理方式就是添加若干出現概率為０的空字元填補在Ｎ叉樹的最下一層，這些權為０的虛結點並無實際意義但卻非常方全便於這棵Ｎ叉樹的建立．空字元的添加個數ａｄｄ的計算如下：Ｙ＝‖Ｓ‖ｍｏｄ（ｎ－１）ａｄｄ＝０（Ｙ＝１）ａｄｄ＝１（Ｙ＝０）ａｄｄ＝Ｎ－Ｙ（Ｙ＞１） 虛結點的加入使得權重最小的Ｎ－ａｄｄ個字元構成了距根結點最遠的分枝，使其它字元構成的Ｎ叉樹保持了豐滿的Ｎ叉結構．例：Ｎ＝３Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ｝Ｗ＝［１，２，３，４，５，６｝則ｙ：＝６ｍｏｄ（３－１）＝０ａｄｄ＝１於是構成Ｎ叉樹如下：�0�2為虛結點�0�3�0�2�0�9�0�3llmＦＥ�0�2�0�9�0�3llmＤＣ�0�2�0�9�0�3ＢＡ�0�2ＷＰＬ＝１＊６＋１＊５＋２＊４＋２＊３＋３＊２＋３＊１＋３＊０＝３３對應編碼為：Ａ：２２１Ｂ：２２０Ｃ：２１Ｄ：２０Ｅ：１Ｆ：０

8. 哈夫曼演算法的概述

1.初始化： 根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權wi的根結點，左右子樹均空。
2. 找最小樹：在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
3. 刪除與加入：在F中刪除這兩棵樹，並將新的二叉樹加入F中。
4. 判斷：重復前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹

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

/*-------------------------------------------------------------------------
*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