1. 哈夫曼樹的基本概念
哈夫曼樹又稱最優(yōu)樹烫映，是一類帶權(quán)路徑長(zhǎng)度最短的樹。
路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑害晦。
路徑長(zhǎng)度：路徑上的分支數(shù)目稱作路徑長(zhǎng)度螃宙。
樹的路徑長(zhǎng)度：從樹根到每一結(jié)點(diǎn)的路徑之和慨仿。
權(quán)：賦予某個(gè)實(shí)體的一個(gè)量，是對(duì)實(shí)體的某個(gè)或某些屬性的數(shù)值描述晒骇。在數(shù)據(jù)結(jié)構(gòu)中霉撵，實(shí)體有結(jié)點(diǎn)（元素）和邊（關(guān)系）兩大類磺浙，所以對(duì)應(yīng)有結(jié)點(diǎn)權(quán)和邊權(quán)。
結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積徒坡。
樹的帶權(quán)路徑長(zhǎng)度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)只和撕氧。
哈夫曼樹：假設(shè)有m個(gè)權(quán)值｛w1,w2,w3,...,wn｝，可以構(gòu)造一棵含有n個(gè)葉子結(jié)點(diǎn)的二叉樹喇完，每個(gè)葉子結(jié)點(diǎn)的權(quán)為wi伦泥，則其中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱做最優(yōu)二叉樹或哈夫曼樹。
2.哈夫曼樹的構(gòu)造算法
(1) 哈夫曼樹的構(gòu)造過(guò)程
(2) 哈夫曼樹的實(shí)現(xiàn)
由于哈夫曼樹中沒(méi)有度為1的結(jié)點(diǎn)锦溪，則一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n -1個(gè)結(jié)點(diǎn)不脯，可以存儲(chǔ)在一個(gè)大小為2n-1的一維數(shù)組中。
weight parent lchild rchild
//哈夫曼樹的存儲(chǔ)表示
typedef struct｛
int weight; //結(jié)點(diǎn)的權(quán)重
int parent,lchild,rchild;//結(jié)點(diǎn)的雙親刻诊、左孩子防楷、右孩子的下標(biāo)
｝HTNode,*HuffmanTree
哈夫曼樹的各結(jié)點(diǎn)存儲(chǔ)由HuffmanTree定義的動(dòng)態(tài)分配的數(shù)組中，為了實(shí)現(xiàn)方便數(shù)組的0號(hào)單元不使用则涯，從1號(hào)單元開(kāi)始使用复局，所以數(shù)組的大小為2n。將葉子結(jié)點(diǎn)集中存儲(chǔ)在前面部分1~n個(gè)位置粟判，而后n-1個(gè)位置存儲(chǔ)其余非葉子結(jié)點(diǎn)亿昏。
- 初始化：首先動(dòng)態(tài)申請(qǐng)2n個(gè)單元，然后循環(huán)2n-1次档礁，從1號(hào)單元開(kāi)始龙优，依次將1至2n-1所有單元中的雙親、左孩子事秀、右孩子的下標(biāo)初始化為0彤断，最后再循環(huán)n次，輸入前n個(gè)單元中葉子的權(quán)值易迹。
- 創(chuàng)建樹：循環(huán)n-1次宰衙，通過(guò)n-1次選擇、刪除與合并來(lái)創(chuàng)建哈夫曼樹睹欲。選擇是從當(dāng)前森林中選擇雙親為0且權(quán)值最小的兩個(gè)樹根結(jié)點(diǎn)s1和s2供炼。刪除是指將結(jié)點(diǎn)s1和s2的雙親改為非0。合并就是將s1和s2的權(quán)值和作為一個(gè)新結(jié)點(diǎn)的權(quán)值依次存入到數(shù)組的第n＋1之后的單元中窘疮，同時(shí)紀(jì)錄這個(gè)新結(jié)點(diǎn)左孩子的下標(biāo)s1袋哼，右孩子的下標(biāo)s2。
// 選擇權(quán)值最小的兩顆樹
void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
{
s1 = s2 = 0;
int i;
for(i = 1; i < n; ++ i){
if(0 == hT[i].parent){
if(0 == s1){
s1 = i;
}
else{
s2 = i;
break;
}
}
}
if(hT[s1].weight > hT[s2].weight){
int t = s1;
s1 = s2;
s2 = t;
}
for(i += 1; i < n; ++ i){
if(0 == hT[i].parent){
if(hT[i].weight < hT[s1].weight){
s2 = s1;
s1 = i;
}else if(hT[i].weight < hT[s2].weight){
s2 = i;
}
}
}
}
// 構(gòu)造有n個(gè)權(quán)值（葉子節(jié)點(diǎn)）的哈夫曼樹
void CreateHufmanTree(HuffmanTree &hT)
{
int n, m;
cin >> n;
m = 2*n - 1;
hT = new HTNode[m + 1]; // 0號(hào)節(jié)點(diǎn)不使用
for(int i = 1; i <= m; ++ i){
hT[i].parent = hT[i].lChild = hT[i].rChild = 0;
}
for(int i = 1; i <= n; ++ i){
cin >> hT[i].weight; // 輸入前n個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值
}
hT[0].weight = m; // 用0號(hào)節(jié)點(diǎn)保存節(jié)點(diǎn)數(shù)量
/****** 初始化完畢, 創(chuàng)建哈夫曼樹 ******/
for(int i = n + 1; i <= m; ++ i){
//通過(guò)n-1次的選擇闸衫、刪除涛贯、合并來(lái)創(chuàng)建二叉樹
int s1, s2;
SelectMin(hT, i, s1, s2);
hT[s1].parent = hT[s2].parent = i;
hT[i].lChild = s1; hT[i].rChild = s2; // 作為新節(jié)點(diǎn)的孩子
hT[i].weight = hT[s1].weight + hT[s2].weight; // 新節(jié)點(diǎn)為左右孩子節(jié)點(diǎn)權(quán)值之和
}
}
C＋＋ 完整代碼
#include <iostream>
#include <iomanip>
using namespace std;
//哈夫曼樹的存儲(chǔ)表示
typedef struct
{
int weight; // 權(quán)值
int parent, lChild, rChild; // 雙親及左右孩子的下標(biāo)
}HTNode, *HuffmanTree;
// 選擇權(quán)值最小的兩顆樹
void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
{
s1 = s2 = 0;
int i;
for(i = 1; i < n; ++ i){
if(0 == hT[i].parent){
if(0 == s1){
s1 = i;
}
else{
s2 = i;
break;
}
}
}
if(hT[s1].weight > hT[s2].weight){
int t = s1;
s1 = s2;
s2 = t;
}
for(i += 1; i < n; ++ i){
if(0 == hT[i].parent){
if(hT[i].weight < hT[s1].weight){
s2 = s1;
s1 = i;
}else if(hT[i].weight < hT[s2].weight){
s2 = i;
}
}
}
}
// 構(gòu)造有n個(gè)權(quán)值（葉子節(jié)點(diǎn)）的哈夫曼樹
void CreateHufmanTree(HuffmanTree &hT)
{
int n, m;
cin >> n;
m = 2*n - 1;
hT = new HTNode[m + 1]; // 0號(hào)節(jié)點(diǎn)不使用
for(int i = 1; i <= m; ++ i){
hT[i].parent = hT[i].lChild = hT[i].rChild = 0;
}
for(int i = 1; i <= n; ++ i){
cin >> hT[i].weight; // 輸入權(quán)值
}
hT[0].weight = m; // 用0號(hào)節(jié)點(diǎn)保存節(jié)點(diǎn)數(shù)量
/****** 初始化完畢, 創(chuàng)建哈夫曼樹 ******/
for(int i = n + 1; i <= m; ++ i){
int s1, s2;
SelectMin(hT, i, s1, s2);
hT[s1].parent = hT[s2].parent = i;
hT[i].lChild = s1; hT[i].rChild = s2; // 作為新節(jié)點(diǎn)的孩子
hT[i].weight = hT[s1].weight + hT[s2].weight; // 新節(jié)點(diǎn)為左右孩子節(jié)點(diǎn)權(quán)值之和
}
}
int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)
{
if(hT[i].lChild == 0 && hT[i].rChild == 0){
return hT[i].weight * deepth;
}
else{
return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);
}
}
// 計(jì)算WPL（帶權(quán)路徑長(zhǎng)度）
int HuffmanTreeWPL(HuffmanTree hT)
{
return HuffmanTreeWPL_(hT, hT[0].weight, 0);
}
// 輸出哈夫曼樹各節(jié)點(diǎn)的狀態(tài)
void Print(HuffmanTree hT)
{
cout << "index weight parent lChild rChild" << endl;
cout << left; // 左對(duì)齊輸出
for(int i = 1, m = hT[0].weight; i <= m; ++ i){
cout << setw(5) << i << " ";
cout << setw(6) << hT[i].weight << " ";
cout << setw(6) << hT[i].parent << " ";
cout << setw(6) << hT[i].lChild << " ";
cout << setw(6) << hT[i].rChild << endl;
}
}
// 銷毀哈夫曼樹
void DestoryHuffmanTree(HuffmanTree &hT)
{
delete[] hT;
hT = NULL;
}
int main()
{
HuffmanTree hT;
CreateHufmanTree(hT);
Print(hT);
cout << "WPL = " << HuffmanTreeWPL(hT) << endl;
DestoryHuffmanTree(hT);
return 0;
}
