一、哈弗曼樹的基本概念。
哈夫曼樹，又稱最優樹，是一類帶權路徑長度最短的樹。下面有幾個概念：
（1）路徑。
樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。
（2）路徑長度。
路徑上的分枝數目。
（3）樹的路徑長度。
從樹根到每一個結點的路徑長度之和。
（4）結點的帶權路徑長度。
從該結點到樹根之間的路徑長度與結點上權的乘積。
（5）樹的帶權路徑長度。
樹中所有葉子節點的帶權路徑長度之和。通常記作：
帶權路徑長度WPL最小的二叉樹叫做最優二叉樹或哈夫曼樹。
二、構造哈夫曼樹。
采用哈夫曼法算法構造過程為：
（1）根據給定的n個權值{w1,w2,…,wn}構成n棵二叉樹的集合F={T1,T2,…,Tn},其中每棵樹Ti中只有一個帶權為wi的根結點，其左右子樹均空。
（2）在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。
（3）在F中刪除這兩棵樹，同時將新得到的二叉樹加入到F中。
（4）重復（2）和（3），直到F只含一棵樹為止。
例如權值為7,5,2,4的結點構造過程為：
------------------------------分割線------------------------------
C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm
讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm
讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm
讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm
將C語言梳理一下，分布在以下10個章節中：
三、編碼和編碼樹。
1、等長編碼和不等長編碼。
（1）等長編碼。
每個字符的編碼長度相同（每個編碼所含的二進制位數相同）。特點是編（譯）碼容易，抗干擾能力強，但長度不是最短，效率低。
（2）不等長編碼。
與等長編碼相對，效率高。若要設計長短不等的編碼（考慮譯碼唯一性），則必須是任一個字符的編碼都不是另一個字符的編碼的前綴，這種編碼稱作前綴編碼。
2、哈夫曼編碼。
考慮利用二叉樹來設計二進制的前綴編碼。約定左分支表示字符0，右分支表示字符1，從根結點到葉子結點的路徑上分支字符組成的字符串作為該葉子結點字符的編碼，可以證明得到的必為二進制前綴碼。
考慮如何得到使電文長度最短的二進制前綴編碼。可以看出，設計電文總長最短的二進制前綴編碼即以n種字符出現的頻率作權，構造一顆哈夫曼樹。
下面給出C++參考代碼：
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>
using namespace std;
struct TNode
{
unsigned int weight;
unsigned int parent;
unsigned int lchild;
unsigned int rchild;
struct TNode() : weight(0), parent(0), lchild(0), rchild(0){}
};
class HuffTree
{
public:
void HuffmanCode(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh);
void HuffDecodeing(vector<TNode> &HT, vector<string> &HC, vector<int> &SrcCode);
private:
void InitHuffTree(vector<TNode> &HT, const vector<int> &wgh);
void BuildHuffTree(vector<TNode> &HT, const vector<int> &wgh);
void SelectTwoMin(vector<TNode> &HT, int n, int &min1, int &min2);
void HuffCodeing(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh);
};
void HuffTree::InitHuffTree(vector<TNode> &HT, const vector<int> &wgh)
{
if (wgh.empty())
{
return;
}
int wghSize = wgh.size();
int m = 2 * wghSize - 1;
HT.resize(m + 1);
for (int i = 1; i <= wghSize; ++i)
{
HT[i].weight = wgh[i - 1];
}
}
void HuffTree::SelectTwoMin(vector<TNode> &HT, int n, int &min1, int &min2)
{
if (HT.empty())
{
return;
}
multimap<int, int> wghMap;
multimap<int, int>::iterator iter;
for (int i = 1; i < n; ++i)
{
if (HT[i].parent == 0)
{
wghMap.insert(make_pair(HT[i].weight, i));
}
}
if (wghMap.size() >= 2)
{
iter = wghMap.begin();
min1 = iter->second;
min2 = (++iter)->second;
}
}
void HuffTree::BuildHuffTree(vector<TNode> &HT, const vector<int> &wgh)
{
if (HT.empty() || wgh.empty())
{
return;
}
int htSize = HT.size();
int wghSize = wgh.size();
int wghs1, wghs2;
for (int i = wghSize + 1; i < htSize; i++)
{
SelectTwoMin(HT, i, wghs1, wghs2);
HT[wghs1].parent = i;
HT[wghs2].parent = i;
HT[i].lchild = wghs1;
HT[i].rchild = wghs2;
HT[i].weight = HT[wghs1].weight + HT[wghs2].weight;
}
}
void HuffTree::HuffCodeing(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh)
{
if (HT.empty() || wgh.empty())
{
return;
}
int n = wgh.size() + 1;
int cha, par;
string codeTmp, code;
for (int i = 1; i < n; i++)
{
code.clear();
codeTmp.clear();
for (cha = i, par = HT[i].parent; par != 0; cha = par, par = HT[par].parent)
{
if (HT[par].lchild == cha)
{
codeTmp = codeTmp + "0";
}
else
{
codeTmp = codeTmp + "1";
}
}
for (int j = codeTmp.size() - 1; j >= 0; --j)
{
code = code + codeTmp[j];
}
HC.push_back(code);
}
}
void HuffTree::HuffDecodeing(vector<TNode> &HT, vector<string> &HC, vector<int> &SrcCode)
{
if (HT.empty() || HC.empty())
{
return;
}
string codeTmp;
int p, strLen;
for (int i = 0; i < HC.size(); ++i)
{
p = HT.size() - 1; //回到根結點
codeTmp = HC[i];
strLen = codeTmp.size();
for (int j = 0; j < strLen; ++j)
{
if (codeTmp[j] == '0')
{
p = HT[p].lchild;
}
else
{
p = HT[p].rchild;
}
}
SrcCode.push_back(HT[p].weight);
}
}
void HuffTree::HuffmanCode(vector<TNode> &HT, vector<string> &HC, const vector<int> &wgh)
{
if (wgh.empty())
{
return;
}
InitHuffTree(HT, wgh);
BuildHuffTree(HT, wgh);
HuffCodeing(HT, HC, wgh);
}
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2015-02/113459p2.htm
