哈夫曼樹演算法

Ⅰ 哈夫曼樹構造演算法中j<n+i是什麼意思

先看一下哈夫曼樹的構造規則是：
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合並，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；
(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

用數據表示哈夫曼樹的話，首先有n個權值點，其初始化就是從 0 到 n -1，先從這裡面查找兩個權值最小的結點，就是遍歷一遍，把最小的值取出來。X1 和X2 要記錄著兩個權值在哪個位置。
然後把這兩個權值加起來的和放回到數組n的位置，然後繼續遍歷這個數據，現在是從0 到n了，當然原來X1 和X2位置的兩個點不用管，已經有父節點了。繼續上述過程直到只有一個節點位置。

如 1 2 3 4 5 6構造哈夫曼樹，先初始化parent 為 -1
1 2 3 4 5 6
parent -1 -1 -1 -1 -1 -1
先從上述中選取兩個權值最小的節點 1 和 2，構造樹變為3，放到數組6的位置，原權值序列變為：
1 2 3 4 5 6 3
parent 6 6 -1 -1 -1 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到3 和 3，放到數組7的位置，權值序列變為：
1 2 3 4 5 6 3 6
parent 6 6 7 -1 -1 -1 7 -1
繼續選取 兩個最小權值且parent為-1的點。找到4 和5，到數組8的位置，權值序列變為：
1 2 3 4 5 6 3 6 9
parent 6 6 7 8 8 -1 7 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到6 和6，到數組9的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12
parent 6 6 7 8 8 9 7 9 -1 -1
繼續選取 兩個最小權值且parent為-1的點。找到9 和12，到數組10的位置，權值序列變為：
1 2 3 4 5 6 3 6 9 12 21
parent 6 6 7 8 8 9 7 9 10 10 -1
結束
所以你說的j < n + i，由於每次選取兩個權值的點權值和做為新的節點放在數組後面，當然下一次循環的時候要多一次循環。
X1 和X2要記錄下選擇兩個權值，將其父節點的位置設置為新的權值點位置。

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

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

Ⅲ 最優二叉樹演算法的構造演算法

從上述演算法中可以看出，F實際上是森林，該演算法的思想是不斷地進行森林F中的二叉樹的「合並」，最終得到哈夫曼樹。
在構造哈夫曼樹時，可以設置一個結構數組HuffNode保存哈夫曼樹中各結點的信息，根據二叉樹的性質可知，具有n個葉子結點的哈夫曼樹共有2n－1個結點，所以數組HuffNode的大小設置為2n－1，數組元素的結構形式如下： weight lchild rchild parent 其中，weight域保存結點的權值，lchild和rchild域分別保存該結點的左、右孩子結點在數組HuffNode中的序號，從而建立起結點之間的關系。為了判定一個結點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。初始時parent的值為－1，當結點加入到樹中時，該結點parent的值為其雙親結點在數組HuffNode中的序號，就不會是－1了。
構造哈夫曼樹時，首先將由n個字元形成的n個葉結點存放到數組HuffNode的前n個分量中，然後根據前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合並為一個較大的子樹，每次構成的新子樹的根結點順序放到HuffNode數組中的前n個分量的後面。
下面給出哈夫曼樹的構造演算法。
const maxvalue= 10000; {定義最大權值}
maxleat=30; {定義哈夫曼樹中葉子結點個數}
maxnode=maxleaf*2-1;
type HnodeType=record
weight: integer;
parent: integer;
lchild: integer;
rchild: integer;
end;
HuffArr:array[0..maxnode] of HnodeType;
var ……
procere CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構造演算法}
var i,j,m1,m2,x1,x2,n: integer;
begin
readln(n); {輸入葉子結點個數}
for i:=0 to 2*n-1 do {數組HuffNode[ ]初始化}
begin
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
end;
for i:=0 to n-1 do read(HuffNode[i].weight); {輸入n個葉子結點的權值}
for i:=0 to n-1 do {構造哈夫曼樹}
begin
m1:=MAXVALUE; m2:=MAXVALUE;
x1:=0; x2:=0;
for j:=0 to n i-1 do
if (HuffNode[j].weight
begin m2:=m1; x2:=x1;
m1:=HuffNode[j].weight; x1:=j;
end
else if (HuffNode[j].weight
begin m2:=HuffNode[j].weight; x2:=j; end;
{將找出的兩棵子樹合並為一棵子樹}
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;
end;
end;