1. 前言

什么是哈夫曼樹？

把權(quán)值不同的n個結(jié)點構(gòu)造成一棵二叉樹，如果此樹滿足以下幾個條件：

• 此 n 個結(jié)點為二叉樹的葉結(jié)點 。
• 權(quán)值較大的結(jié)點離根結(jié)點較近，權(quán)值較小的結(jié)點離根結(jié)點較遠(yuǎn)。
• 該樹的帶權(quán)路徑長度是所有可能構(gòu)建的二叉樹中最小的。

則稱符合上述條件的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。

構(gòu)建哈夫曼樹的目的是什么？

用來解決在通信系統(tǒng)中如何使用最少的二進(jìn)制位編碼字符信息。

本文將和大家聊聊哈夫曼樹的設(shè)計思想以及構(gòu)建過程。

2. 設(shè)計思路

哈夫曼樹產(chǎn)生的背景：

在通信系統(tǒng)中傳遞一串字符串文本時，需要對這一串字符串文本信息進(jìn)行二進(jìn)制編碼。編碼時如何保證所用到的bit位是最少的，或保證整個編碼后的傳輸長度最短。

現(xiàn)假設(shè)字符串由ABCD 4個字符組成，最直接的想法是使用 2 個bit位進(jìn)行等長編碼，如下表格所示：

傳輸ABCD字符串一次時，所需bit為 2位，當(dāng)通信次數(shù)達(dá)到 n次時，則需要的總傳輸長度為 n*2。當(dāng)字符串的傳輸次數(shù)為 1000次時，所需要傳輸?shù)目傞L度為 2000個bit。

使用等長編碼時，如果傳輸?shù)膱笪闹杏?nbsp;26 個不同字符時，因需要對每一個字符進(jìn)行編碼，至少需要 5位bit。

但在實際應(yīng)用中，各個字符的出現(xiàn)頻率或使用次數(shù)是不相同的，如A、B、C的使用頻率遠(yuǎn)遠(yuǎn)高于X、Y、Z。使用等長編碼特點是無論字符出現(xiàn)的頻率差異有多大，每一個字符都得使用相同的bit位。

哈夫曼的設(shè)計思想：

• 對字符串信息進(jìn)行編碼設(shè)計時，讓使用頻率高的字符使用短碼，使用頻率低的用長碼，以優(yōu)化整個信息編碼的長度。
• 基于這種簡單、樸素的想法設(shè)計出來的編碼也稱為不等長編碼。

哈夫曼不等長編碼的具體思路如下：

如現(xiàn)在要發(fā)送僅由A、B、C、D 4 個字符組成的報文信息 ，A字符在信息中占比為 50%，B的占比是 20%，C的占比是 15%， D的 占比是10%。

不等長編碼的樸實思想是字符的占比越大，所用的bit位就少，占比越小，所用bit位越多。如下為每一個字符使用的bit位數(shù)：

• A使用 1位bit編碼。
• B使用 2 位 bit編碼。
• C 使用 3 位 bit編碼。
• D 使用 3 位 bit 編碼。

具體編碼如下表格所示：

如此編碼后，是否真的比前面的等長編碼所使用的總bit位要少？

計算結(jié)果=0.5*1+0.2*2+0.15*3+0.1*3=1.65。

先計算每一個字符在報文信息中的占比乘以字符所使用的bit位。

然后對上述每一個字符計算后的結(jié)果進(jìn)行相加。

顯然，編碼ABCD只需要 1.65 個bit ，比等長編碼用到的2 個 bit位要少 。當(dāng)傳輸信息量為 1000時，總共所需要的bit位=1.65*1000=1650 bit。

哈夫曼編碼和哈夫曼樹有什么關(guān)系？

因為字符的編碼是通過構(gòu)建一棵自下向上的二叉樹推導(dǎo)出來的，如下圖所示：

哈夫曼樹的特點：

• 信息結(jié)點都是葉子結(jié)點。
• 葉子結(jié)點具有權(quán)值。如上二叉樹，A結(jié)點權(quán)值為0.5，B結(jié)點權(quán)值為0.2，C結(jié)點權(quán)值為0.15，D結(jié)點權(quán)值為 0.1。
• 哈夫曼編碼為不等長前綴編碼（即要求一個字符的編碼不能是另一個字符編碼的前綴）。
• 從根結(jié)點開始，為左右分支分別編號0和1，然后順序連接從根結(jié)點到葉結(jié)點所有分支上的編號得到字符的編碼。

相信大家對哈夫曼樹有了一個大概了解，至于如何通過構(gòu)建哈夫曼樹，咱們繼續(xù)再聊。

3. 構(gòu)建思路

在構(gòu)建哈夫曼樹之前，先了解幾個相關(guān)概念：

• 路徑和路徑長度：在一棵樹中，從一個結(jié)點往下可以達(dá)到的孩子或?qū)O子結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。
• 結(jié)點的權(quán)及帶權(quán)路徑長度：若將樹中結(jié)點賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。
• 樹的帶權(quán)路徑長度：樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和，記為WPL。

如有權(quán)值為{3,4,9,15}的 4 個結(jié)點，則可構(gòu)造出不同的二叉樹，其帶權(quán)路徑長度也會不同。如下 3 種二叉樹中，B的樹帶權(quán)路徑長度是最小的。

哈夫曼樹的構(gòu)建過程就是要保證樹的帶權(quán)路徑長度最小。

那么，如何構(gòu)建二叉樹，才能保證構(gòu)建出來的二叉樹的帶權(quán)路徑長度最小？

如有一字符串信息由 ABCDEFGH 8個字符組成，每一個字符的權(quán)值分別為{3,6,12,9,4,8,21,22}，構(gòu)建最優(yōu)哈夫曼樹的流程：

1.以每一個結(jié)點為根結(jié)點構(gòu)建一個單根二叉樹，二叉樹的左右子結(jié)點為空，根結(jié)點的權(quán)值為每個結(jié)點的權(quán)值。并存儲到一個樹集合中。

2.從樹集合中選擇根結(jié)點的權(quán)值最小的 2 個樹。重新構(gòu)建一棵新二叉樹，讓剛選擇出來的2 棵樹的根結(jié)點成為這棵新樹的左右子結(jié)點，新樹的根結(jié)點的權(quán)值為 2 個左右子結(jié)點權(quán)值的和。構(gòu)建完成后從樹集合中刪除原來 2個結(jié)點，并把新二叉樹放入樹集合中。

如下圖所示。權(quán)值為 3和4的結(jié)點為新二叉樹的左右子結(jié)點，新樹根結(jié)點的權(quán)值為7。

3.重復(fù)第二步，直到樹集合中只有一個根結(jié)點為止。

當(dāng)集合中只存在一個根結(jié)點時，停止構(gòu)建，并且為最后生成樹的每一個非葉子結(jié)點的左結(jié)點分支標(biāo)注0，右結(jié)點分支標(biāo)注1。如下圖所示：

通過上述從下向上的思想構(gòu)建出來的二叉樹，可以保證權(quán)值較小的結(jié)點離根結(jié)點較遠(yuǎn)，權(quán)值較大的結(jié)點離根結(jié)點較近。最終二叉樹的帶權(quán)路徑長度： WPL=(3+4)*5+6*4+(8+9+12)*3+(21+22)*2=232 。并且此樹的帶權(quán)路徑長度是所有可能構(gòu)建出來的二叉樹中最小的。

上述的構(gòu)建思想即為哈夫曼樹設(shè)計思想，不同權(quán)值的字符編碼就是結(jié)點路徑上0和1的順序組合。如下表所述，權(quán)值越大，其編碼越小，權(quán)值越小，其編碼越大。其編碼長度即從根結(jié)點到此葉結(jié)點的路徑長度。

4. 編碼實現(xiàn)

4.1 使用優(yōu)先隊列

可以把權(quán)值不同的結(jié)點分別存儲在優(yōu)先隊列（Priority Queue）中，并且給與權(quán)重較低的結(jié)點較高的優(yōu)先級（Priority）。

具體實現(xiàn)哈夫曼樹算法如下：

1.把n個結(jié)點存儲到優(yōu)先隊列中，則n個節(jié)點都有一個優(yōu)先權(quán)Pi。這里是權(quán)值越小，優(yōu)先權(quán)越高。

2.如果隊列內(nèi)的節(jié)點數(shù)>1，則：

• 從隊列中移除兩個最小的結(jié)點。
• 產(chǎn)生一個新節(jié)點，此節(jié)點為隊列中移除節(jié)點的父節(jié)點，且此節(jié)點的權(quán)重值為兩節(jié)點之權(quán)值之和，把新結(jié)點加入隊列中。
• 重復(fù)上述過程，最后留在優(yōu)先隊列里的結(jié)點為哈夫曼樹的根節(jié)點（root）。

完整代碼：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//樹結(jié)點
struct TreeNode {
	//結(jié)點權(quán)值
	float weight;
	//左結(jié)點
	TreeNode *lelfChild;
	//右結(jié)點
	TreeNode *rightChild;
    //初始化
	TreeNode(float w) {
		weight=w;
		lelfChild=NULL;
		rightChild=NULL;
    }
};
//為優(yōu)先隊列提供比較函數(shù)
struct comp {
	bool operator() (TreeNode * a, TreeNode * b) {
        //由大到小排列
		return a->weight > b->weight; 
	}
};

//哈夫曼樹類
class HfmTree {
	private:
         //優(yōu)先隊列容器
		priority_queue<TreeNode *,vector<TreeNode *>,comp> hfmQueue;
	public:
		//構(gòu)造函數(shù)，構(gòu)建單根結(jié)點樹
		HfmTree(int weights[8]) {
			for(int i=0; i<8; i++) {
				//創(chuàng)建不同權(quán)值的單根樹
				TreeNode *tn=new TreeNode(weights[i]);
				hfmQueue.push(tn);
			}
		}
		//顯示隊列中的最一個結(jié)點
		TreeNode* showHfmRoot() {
			TreeNode *tn;
			while(!hfmQueue.empty()) {
				tn= hfmQueue.top();
				hfmQueue.pop();
			}
			return tn;
		}
		//構(gòu)建哈夫曼樹
		void create() {
             //重復(fù)直到隊列中只有一個結(jié)點
			while(hfmQueue.size()!=1) {
				//從優(yōu)先隊列中找到權(quán)值最小的 2 個單根樹
				TreeNode *minFirst=hfmQueue.top();
				hfmQueue.pop();
				TreeNode *minSecond=hfmQueue.top();
				hfmQueue.pop();
				//創(chuàng)建新的二叉樹
				TreeNode *newRoot=new TreeNode(minFirst->weight+minSecond->weight);
				newRoot->lelfChild=minFirst;
				newRoot->rightChild=minSecond;
				//新二叉樹放入隊列中
				hfmQueue.push(newRoot);
			}
		}
		//按前序遍歷哈夫曼樹的所有結(jié)點
		void showHfmTree(TreeNode *root) {
			if(root!=NULL) {
				cout<<root->weight<<endl;
				showHfmTree(root->lelfChild);
				showHfmTree(root->rightChild);
			}
		}
		//析構(gòu)函數(shù)
		~HfmTree() {
            //省略
		}
};

//測試
int main(int argc, char** argv) {
	//不同權(quán)值的結(jié)點
	int weights[8]= {3,6,12,9,4,8,21,22};
    //調(diào)用構(gòu)造函數(shù)
	HfmTree hfmTree(weights);
    //創(chuàng)建哈夫曼樹
	hfmTree.create();
    //前序方式顯示哈夫曼樹
	TreeNode *root= hfmTree.showHfmRoot();
	hfmTree.showHfmTree(root);
	return 0;
}

顯示結(jié)果：

上述輸出結(jié)果，和前文的演示結(jié)果是一樣的。

此算法的時間復(fù)雜度為O（nlogn）。因為有n個結(jié)點，所以樹總共有2n-1個節(jié)點，使用優(yōu)先隊列每個循環(huán)須O（log n）。

4.2 使用一維數(shù)組

除了上文的使用優(yōu)先隊列之外，還可以使用一維數(shù)組的存儲方式實現(xiàn)。

在哈夫曼樹中，葉子結(jié)點有 n個，非葉子結(jié)點有 n-1個，使用數(shù)組保存哈夫曼樹上所的結(jié)點需要 2n-1個存儲空間 。其算法思路和前文使用隊列的思路差不多。直接上代碼：

#include <iostream>
using namespace std;
//葉結(jié)點數(shù)量
const unsigned int n=8;
//一維數(shù)組長度
const unsigned int m= 2*n -1;
//樹結(jié)點
struct TreeNode {
	//權(quán)值
	float weight;
	//父結(jié)點
	int parent;
	//左結(jié)點
	int leftChild;
	//右結(jié)點
	int rightChild;
};
class HuffmanTree {
	public:
		//創(chuàng)建一維數(shù)組
		TreeNode hfmNodes[m+1];
	public:
		//構(gòu)造函數(shù)
		HuffmanTree(int weights[8]);
		~HuffmanTree( ) {

		}
		void findMinNode(int k, int &s1, int &s2);
		void showInfo() {
			for(int i=0; i<m; i++) {
				cout<<hfmNodes[i].weight<<endl;
			}
		}
};
HuffmanTree::HuffmanTree(int weights[8]) {
	//前2 個權(quán)值最小的結(jié)點
	int firstMin;
	int  secondMin;
	//初始化數(shù)組中的結(jié)點
	for(int i = 1; i <= m; i++) {
		hfmNodes[i].weight = 0;
		hfmNodes[i].parent = -1;
		hfmNodes[i].leftChild = -1;
		hfmNodes[i].rightChild = -1;
	}
	//前 n 個是葉結(jié)點
	for(int i = 1; i <= n; i++)
		hfmNodes[i].weight=weights[i-1];

	for(int i = n + 1; i <=m; i++) {
		this->findMinNode(i-1, firstMin, secondMin);
		hfmNodes[firstMin].parent = i;
		hfmNodes[secondMin].parent = i;
		hfmNodes[i].leftChild = firstMin;
		hfmNodes[i].rightChild = secondMin;
		hfmNodes[i].weight = hfmNodes[firstMin].weight + hfmNodes[secondMin].weight;
	}
}
void HuffmanTree::findMinNode(int k, int & firstMin, int & secondMin) {
	hfmNodes[0].weight = 32767;
	firstMin=secondMin=0;
	for(int i=1; i<=k; i++) {
		if(hfmNodes[i].weight!=0 && hfmNodes[i].parent==-1) {
			if(hfmNodes[i].weight < hfmNodes[firstMin].weight) { 
                  //如果有比第一小還要小的，則原來的第一小變成第二小
				secondMin = firstMin;
                  //新的第一小
				firstMin = i;
			} else if(hfmNodes[i].weight < hfmNodes[secondMin].weight)
			    //如果僅比第二小的小	
                 secondMin = i;
		}
	}
}

int main() {
	int weights[8]= {3,6,12,9,4,8,21,22};
	HuffmanTree huffmanTree(weights);
	huffmanTree.showInfo();
	return 1;
}

測試結(jié)果：

5. 總結(jié)

哈夫曼樹是二叉樹的應(yīng)用之一，掌握哈夫曼樹的建立和編碼方法對解決實際問題有很大幫助。

以上就是漫談C++哈夫曼樹的原理及實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++哈夫曼樹的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論