哈夫曼樹生成演算法java

『壹』 哈夫曼編碼的演算法代碼是什麼

// 哈夫曼編碼(演算法)#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char *HuffmanCode; //動態分配數組，存儲哈夫曼編碼typedef struct
{
unsigned int weight; //用來存放各個結點的權值
unsigned int parent,LChild,RChild; //指向雙親、孩子結點的指針
} HTNode, *HuffmanTree; //動態分配數組，存儲哈夫曼樹//選擇兩個parent為0，且weight最小的結點s1和s2
void Select(HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s2=min;
}//構造哈夫曼樹ht。w存放已知的n個權值
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n)
{
int m,i,s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1; i<=n; i++) //1--n號存放葉子結點，初始化
{
(*ht)[i].weight=w[i];
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
}
for(i=n+1; i<=m; i++)
{
(*ht)[i].weight=0;
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
} //非葉子結點初始化
printf("\nHuffmanTree: \n");
for(i=n+1; i<=m; i++) //創建非葉子結點，建哈夫曼樹
{
//在(*ht)[1]~(*ht)[i-1]的范圍內選擇兩個parent為0
//且weight最小的結點，其序號分別賦值給s1、s2
Select(ht,i-1,&s1,&s2);
(*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("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);
}
printf("\n");
} //哈夫曼樹建立完畢//從葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i,start,p;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n個編碼的頭指針
cd=(char *)malloc(n*sizeof(char)); //分配求當前編碼的工作空間
cd[n-1]='\0'; //從右向左逐位存放編碼，首先存放編碼結束符
for(i=1; i<=n; i++) //求n個葉子結點對應的哈夫曼編碼
{
start=n-1; //初始化編碼起始指針
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //從葉子到根結點求編碼
if( (*ht)[p].LChild==c)
cd[--start]='0'; //左分支標0
else
cd[--start]='1'; //右分支標1
hc[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個編碼分配空間
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1; i<=n; i++)
printf("HuffmanCode of %3d is %s\n",(*ht)[i].weight,hc[i]);
printf("\n");
}void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,i,n,wei,m;
printf("\nn = " );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
printf("\ninput the %d element's weight:\n",n);
for(i=1; i<=n; i++)
{
printf("%d: ",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
CrtHuffmanCode(&HT,&HC,n);
}

『貳』 哈夫曼樹演算法

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

『叄』 數據結構求赫夫曼樹的演算法

#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;
}

不知道是不是你要的

『肆』 哈夫曼樹編碼的應用（java語言）

1）編寫函數實現選擇parent為0且權值最小的兩個根結點的演算法
2）編寫函數實現統計字元串中字元的種類以及各類字元的個數。
3）編寫函數構造赫夫曼樹。
4）編寫函數實現由赫夫曼樹求赫夫曼編碼表。
5）編寫函數實現將正文轉換為相應的編碼文件。
6）編寫函數實現將編碼文件進行解碼。
7）編寫主控函數，完成本實驗的功能。

『伍』 哈夫曼樹

轉自： http://blog.csdn.net/hikvision_java_gyh/article/details/8952596
哈夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的帶權路徑長度記為WPL=(W1 L1+W2 L2+W3 L3+...+ Wn Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。【例】給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權路徑長度分別為: (a)WPL=7 2+5 2+2 2+4 2=36 (b)WPL=7 3+5 3+2 1+4 2=46 (c)WPL=7 1+5 2+2 3+4 3=35其中(c)樹的WPL最小，可以驗證，它就是哈夫曼樹。

構造哈夫曼樹的演算法如下： 1）對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。 2）在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。 3）從F中刪除這兩棵樹，並把這棵新的二叉樹同樣以升序排列加入到集合F中。 4）重復2）和3），直到集合F中只有一棵二叉樹為止。 例如，對於4個權值為1、3、5、7的節點構造一棵哈夫曼樹，其構造過程如下圖所示：

可以計算得到該哈夫曼樹的路徑長度WPL＝(1+3) 3+2 5+1*7=26。
哈夫曼編碼應用 大數據 量的圖像信息會給存儲器的存儲容量，通信干線信道的帶寬，以及計算機的處理速度增加極大的壓力。單純靠增加存儲器容量，提高信道帶寬以及計算機的處理速度等方法來解決這個問題是不現實的，這時就要考慮壓縮。壓縮的關鍵在於編碼，如果在對數據進行編碼時，對於常見的數據，編碼器輸出較短的碼字；而對於少見的數據則用較長的碼字表示，就能夠實現壓縮。【例】：假設一個文件中出現了8種符號S0，SQ，S2，S3，S4，S5，S6，S7，那麼每種符號要編碼，至少需要3bit。假設編碼成 000，001， 010，011，100，101，110，111。那麼符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼後變成 ，共用了42bit。我們發現S0，S1，S2這3個符號出現的頻率比較大，其它符號出現的頻率比較小，我們採用這樣的編碼方案：S0到S7的碼遼分別01，11，101，0000，0001，0010，0011， 100，那麼上述符號序列變成，共用了39bit。盡管有些碼字如 S3，S4，S5，S6變長了(由3位變成4位)，但使用頻繁的幾個碼字如S0，S1變短了，所以實現了壓縮。對於上述的編碼可能導致解碼出現非單值性：比如說，如果S0的碼字為01，S2的碼字為011，那麼當序列中出現011時，你不知道是S0的碼字後面跟了個1，還是完整的一個S2的碼字。因此，編碼必須保證較短的編碼決不能是較長編碼的前綴。符合這種要求的編碼稱之為前綴編碼。要構造符合這樣的二進制編碼體系，可以通過二叉樹來實現。以下是哈夫曼樹的 Java 實現：
[java] view plain

// 二叉樹節點
public class Node implements Comparable { private int value; private Node leftChild; private Node rightChild; public Node(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } public int compareTo(Object o) { Node that = (Node) o; double result = this.value - that.value; return result > 0 ? 1 : result == 0 ? 0 : -1; } }

private static Node build(List<Node> nodes) {
nodes = new ArrayList<Node>(nodes);
sortList(nodes);
while (nodes.size() > 1) {
createAndReplace(nodes);
}
return nodes.get(0);
}

/**

/**

private static void sortList(List<Node> nodes) {
Collections.sort(nodes);
}

`
/**

『陸』 Java實現哈夫曼演算法，運行出現問題，求幫助，在線等！！！

可以在Dog與Cat類中重寫Animal中的animalDo方法，通過調用animalDo方法，

然後會自動根據不同的實例調用不同類中的方法（多態知識）。

『柒』 到底什麼是哈夫曼樹啊，求例子

哈夫曼樹是給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

例子：

1、將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

2、 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

3、從森林中刪除選取的兩棵樹，並將新樹加入森林；

4、重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

(7)哈夫曼樹生成演算法java擴展閱讀：

按照哈夫曼編碼構思程序流程：

1、切割的順序是從上往下，直至數組中的元素全部出現在葉節點；

2、我們思路正好相反，從數組中找出最小的兩個元素作為最下面的葉節點，在向備選數組中存入這兩個葉節點的和（這個新的和加入累加運算，這個和也就是所求的最小值的一部分，原因如上圖）。

3、以本題為例，備選數組中現有元素為{30，30}，再次取出兩個最小元素進行求和，得到新的元素，回歸備選數組並記入累加。

4、上述2.3布重復執行直至備選數組中只有一個元素，此時累加結束，返回累加值即可

5、求數組中的最小值，可以用小根堆進行提取最為方便；此題用到了貪心的思路，即用相同的策略重復執行，直至我們得到所需的結果。