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-1次的“合並”運算後構造出最終所要求的樹，即哈夫曼樹，它的核心思想是讓權值大的葉子離根最近。每次從樹的集合中取出雙親為0且權值最小的兩棵樹作為左、右子樹，構造一棵新樹，新樹根結點的權值為其左右孩子結點權之和，將新樹插入到樹的集合中。
算法設計
步驟1：確定合適的數據結構。
步驟2：初始化。構造n棵結點為n個字符的單結點樹集合F={T1，T2,…, Tn}，每棵樹中隻有一個帶權的根結點，權值為該字符的使用頻率；
步驟3：如果F中隻剩下一棵樹，則哈夫曼樹構造成功，轉步驟6；否則，從集合F中取出雙親為0且權值最小的兩棵樹Ti和Tj，將它們合並成一棵新樹Zk，新樹以Ti為左兒子， Tj為右兒子（反之也可以）。新樹Zk的根結點的權值為Ti與Tj的權值之和；
步驟4：從集合F中刪去Ti、Tj，加入Zk；
步驟5：重復步驟3和4；
步驟6：從葉子結點到根結點逆向求出每個字符的哈夫曼編碼（約定左分支表示字符“0”，右分支表示字符“1”）。則從根結點到葉子結點路徑上的分支字符組成的字符串即為葉子字符的哈夫曼編碼。算法結束。
構造實例
已知某系統在通信聯絡中隻可能出現8種字符，分別為a，b，c，d，e，f，g，h，其使用頻率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設計哈夫曼編碼。設權w=(5，29，7，8，14，23，3，11)，n=8，按哈夫曼算法的設計步驟構造一棵哈夫曼編碼樹，具體過程如下：
理解代碼
源碼：
#include <iostream>
using namespace std;
#define N 8
struct Node
{
char L;//字母
int K;//權值
bool IsRoot;//是否為根結點
int Lc, Rc;//左右子樹
Node(char l = '/0', int k = 0, bool isRoot = false) {
L = l; K = k; IsRoot = isRoot; Lc = Rc = -1;
}
};
Node A[N + N - 1] = { Node('a',5,true) , Node('b',29,true), Node('c',7,true), Node('d',8,true),
Node('e',14,true), Node('f',23,true), Node('g',3,true), Node('h',11,true) };
void FindMin(Node A[], int &min1, int &min2,int num)
{
min1 = num - 1;
for (int i = 0; i < num; i++) {
if (A[i].IsRoot && A[i].K < A[min1].K) min1 = i;
}
min2 = num - 1;
for (int i = 0; i < num; i++) {
if (min1 != i && A[i].IsRoot &&A[i].K < A[min2].K) min2 = i;
}
}
int main()
{
int y = 1, num = N;
int min1=0, min2=0;
for (int i = 0; i < N; i++) {
FindMin(A,min1,min2,num);
A[num].K = A[min1].K + A[min2].K;
A[num].Lc = min1;
A[num].Rc = min2;
A[num].IsRoot = true;
A[min1].IsRoot = false;
A[min2].IsRoot = false;
A[num].L = 'h' + y;
y++; num++;
}
cout << "最終權值為：" << A[14].K << endl;
}
確定結構體
首先我們創建結點 Node 結構體，並給他定義瞭五個屬性，分別是字符、權值、佈爾型根結點標志、以及左右子樹。隨後直接定義Node類型數組Node(char l,int k,bool isRoot)，初始化Node A數組的長度為 N+N-1的原因是：選取兩個最小權值生成新的結點，並把結點放入A數組中，相當於每兩個結點會多生成一個節點，那麼n個結點就會生成n-1個結點，總數就是n+n-1；我們依次把八個結點放入數組中，並把IsRoot置為true，初始結點均沒有參加生成新節點，都是根結點。
循環找出最小值
將A傳入找最小值的函數，初始num為N，隨著新節點的生成，逐漸++，然後默認最小值為數組的最後一個元素，利用一重for循環遍歷出最小值和次小值，這裡註意，找出的最小值必須是根結點才可以，參加過生成新結點的都要把IsRoot設為false，次小值就是在不等於最小值的情況下找出最小值。
調用細節
主函數中利用一重for循環調用FindMin函數找出兩個最小權值結點並默認放到數組的num位置上，即為最後一個位置；首先新節點的權值由兩個最小權值相加，並把新節點的左右子樹設為找到的兩個最小權值結點，由於結構體數組默認IsRoot為false，所有要把新節點設為根結點，而把用過的結點取消根結點身份，L用來更換結點的字符，最後num++,y++都很好理解，經過七次新節點的生成，我們不難猜到A[14]的權值k為100；
調試試圖
通過調試界面可以看到第一個生成的A[8]結點的左右子樹是A[0]和A[6]，而且權值正好是他們兩個結點的權相加；
A[9]的k是新的兩個最小根結點A[2]和A[8]組成的，可以確認權值沒有問題，A[8]能參加新節點的合成說明我們成功的把他設置為瞭根結點，然後直接看最後一個結點的信息；
權值正確為100，是根節點，因為隻有一個根結點，沒法繼續合成新節點，程序結束。
總結
哈夫曼在算法和數據結構中都挺重要的，隻是不同場景下實現的方法和形式會有所不同，但就算千變萬化也離不開最基礎的“二合一”形式，我提出的這個哈夫曼是不難理解的，希望對大傢有所幫助，共同進步！！！
到此這篇關於C++使用數組來實現哈夫曼樹的文章就介紹到這瞭,更多相關C++哈夫曼樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！