1. 前言

什么是哈夫曼樹？

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

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

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

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

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

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

2. 設(shè)計(jì)思路

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

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

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

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

使用等長編碼時(shí)，如果傳輸?shù)膱?bào)文中有?26?個(gè)不同字符時(shí)，因需要對每一個(gè)字符進(jìn)行編碼，至少需要?5位bit。

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

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

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

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

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

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

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

具體編碼如下表格所示：

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

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

先計(jì)算每一個(gè)字符在報(bào)文信息中的占比乘以字符所使用的bit位。

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

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

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

因?yàn)樽址木幋a是通過構(gòu)建一棵自下向上的二叉樹推導(dǎo)出來的，如下圖所示：

哈夫曼樹的特點(diǎn)：

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

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

3. 構(gòu)建思路

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

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

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

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

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

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

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

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

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

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

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

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

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

4. 編碼實(shí)現(xiàn)

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

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

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

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

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

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

完整代碼：

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

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

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

4.2 使用一維數(shù)組

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

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

#include <iostream>
using namespace std;
//葉結(jié)點(diǎn)數(shù)量
const unsigned int n=8;
//一維數(shù)組長度
const unsigned int m= 2*n -1;
//樹結(jié)點(diǎn)
struct TreeNode {
	//權(quán)值
	float weight;
	//父結(jié)點(diǎn)
	int parent;
	//左結(jié)點(diǎn)
	int leftChild;
	//右結(jié)點(diǎn)
	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 個(gè)權(quán)值最小的結(jié)點(diǎn)
	int firstMin;
	int  secondMin;
	//初始化數(shù)組中的結(jié)點(diǎn)
	for(int i = 1; i <= m; i++) {
		hfmNodes[i].weight = 0;
		hfmNodes[i].parent = -1;
		hfmNodes[i].leftChild = -1;
		hfmNodes[i].rightChild = -1;
	}
	//前 n 個(gè)是葉結(jié)點(diǎn)
	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)用之一，掌握哈夫曼樹的建立和編碼方法對解決實(shí)際問題有很大幫助。