1 基本概念
赫夫曼树（Huffman Tree）又称为最优树，是一类带权路径长度最短的树。本文仅讨论最优二叉树。
树的路径长度是指从树根到树中其余各个结点的路径长度之和。对具有n个结点的二叉树而言，完全二叉树具有最短的树的路径长度。
若在二叉树中，树叶结点带有权值，则有：结点的带权路径长度定义为从树根到该结点之间的路径长度与该结点上所带权值之积。
若树中有n个树叶结点，且每个树叶结点均带有权值，则有：树的带权路径长度定义为树中所有树叶结点的带权路径长度之和，可记为：
有时，也将树的路径长度称为内路径长度，而将树的带权路径长度称为树的外路径长度。
构造最优树的赫夫曼算法：
①根据给定的n个权值，构成n棵二叉树的集合F，其中每棵树中只有一个带有权值的根结点，其左右子树均为空树。
②在F中选取两棵根结点的权值最小的树，并以它们作为左右子树构造一棵新的二叉树，且置新的二叉树根结点的权值为其左、右子树上根结点的权值之和。
③在F中删除这两棵树，同时将新得到的二叉树加入F中。
重复②③步骤，知道F只含一棵树而知。这棵树便是所求的的赫夫曼树。
2 赫夫曼树实现
具有n个树叶结点的赫夫曼（二叉）树总的结点个数为2n-1。由于树中的结点个数是确定的，因此，选择静态树表作为存储结构，结合即将讨论的赫夫曼编码，最终选择静态三叉树表作为建立赫夫曼树的存储结构。静态三叉树表结点结构如下：
struct HTnode
{
char ch;
int weight,parent,lchild,rchild;
};HuffmanTree类声明如下：
#pragma once
#define MAXSIZE 1000
#include "HTnode.h"
#include <windows.h>
class HuffmanTree
{
friend class HuffmanCoder;
public:
HuffmanTree(int n,char chA[],int weightA[]):m_HTsize(0),m_HT(NULL)
{
_Create(n,chA,weightA);
}
~HuffmanTree()
{
delete [] m_HT;
}
void Display();
private:
int m_HTsize; //树叶结点个数
HTnode* m_HT;
void _Create(int,char chA[],int weightA[]);
int _MinVal(const int&);
void _Select(const int,int&,int&);
};HuffmanTree类实现如下：
#include "HuffmanTree.h"
#include <iostream>
using namespace std;
void HuffmanTree::_Create(int n,char chA[],int weightA[])
{
int i, s1, s2;
m_HTsize = 2 * n - 1;
m_HT = new HTnode[2 * n - 1];
if (n <= 1)
{
return;
}
for (i = 0; i < n; i++)
{
m_HT[i].ch = chA[i];
m_HT[i].weight = weightA[i];
m_HT[i].parent = -1;
m_HT[i].lchild = -1;
m_HT[i].rchild = -1;
}
while(i < m_HTsize)
{
_Select(i,s1,s2);
m_HT[s1].parent = m_HT[s2].parent = i;
m_HT[i].lchild = s1;
m_HT[i].rchild = s2;
m_HT[i].weight = m_HT[s1].weight + m_HT[s2].weight;
m_HT[i].parent = -1;
i++;
}
}
void HuffmanTree::Display()
{
int i;
std::cout<<"所建立的赫夫曼树的静态链表表示如下："<<std::endl;
std::cout<<"位置\t"<<"字符\t"<<"权值\t"<<"双亲\t"<<"左孩子\t"<<"右孩子"<<endl;
for (i = 0; i < (m_HTsize + 1) / 2; i++)
{
cout<<i<<"\t"<<m_HT[i].ch<<"\t"<<m_HT[i].weight<<"\t"<<m_HT[i].parent
<<"\t"<<m_HT[i].lchild<<"\t"<<m_HT[i].rchild<<endl;
}
while (i < m_HTsize)
{
cout<<i<<"\t\t"<<m_HT[i].weight<<"\t"<<m_HT[i].parent<<"\t"<<m_HT[i].lchild
<<"\t"<<m_HT[i].rchild<<endl;
i++;
}
}
//从前i个结点中选择parent为-1且weight最小的结点，获取其序号
int HuffmanTree::_MinVal(const int& i)
{
int j, k, min = MAXSIZE;
for (j = 0; j < i; j++)
{
if (m_HT[j].parent == -1 && m_HT[j].weight < min)
{
min = m_HT[i].weight;
k = j;
}
}
m_HT[k].parent = MAXSIZE;
return k;
}
void HuffmanTree::_Select(const int i,int& s1,int& s2)
{
int s;
s1 = _MinVal(i);
s2 = _MinVal(i);
if (s1 > s2)
{
s = s1;
s1 = s2;
s2 = s;
}
}
3 赫夫曼树编码
赫夫曼树的一个重要应用是在通信中构造最优的前缀编码，从而使得电文长度达到最短。
通常有两类二进制编码：
①等长编码：编码的二进制长度取决于电文中出现的字符个数。
②不等长编码：各字符的二进制编码长度不等。它的好处是可以使传送电文的字符串总长度尽可能的短。
通常各个字符在电文中出现的次数是不相同的，若对出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。
在实用的不等长编码中，任一一个字符的编码都不能是另一个字符编码的前缀，这种编码成为前缀编码。
赫夫曼编码表的结点结构定义如下：
//赫夫曼编码表结点结构
struct HCnode
{
char ch;
char* pstring;
};赫夫曼编码类实现如下：
//HuffmanCoder.h
#pragma once
#include "HCnode.h"
#include "HuffmanTree.h"
class HuffmanCoder
{
public:
HuffmanCoder(const int& n)
{
m_HC = new HCnode[n];
m_HCsize = n;
}
~HuffmanCoder()
{
for (int i = 0; i < m_HCsize; i++)
{
delete [] m_HC[i].pstring;
}
delete [] m_HC;
}
void CreateBook(HuffmanTree&);
void Coder(char ch[]);
void Decoder(HuffmanTree&);
private:
HCnode* m_HC; //赫夫曼编码表基地址指针
int m_HCsize; //外结点个数
};
//HuffmanCoder.cpp
#include "HuffmanCoder.h"
#include <iostream>
#include <fstream>
using namespace std;
void HuffmanCoder::CreateBook(HuffmanTree& ht)
{
int i,j,c,f,start;
char* cd = new char[m_HCsize];
cd[m_HCsize-1] = '\0';
cout<<"以下是各字符的赫夫曼编码："<<endl;
for (i = 0; i < m_HCsize; i++)
{
start = m_HCsize - 1;
m_HC[i].ch = ht.m_HT[i].ch;
for (c = i, f = ht.m_HT[i].parent; f !=-1; c = f, f = ht.m_HT[f].parent)
{
if (ht.m_HT[f].lchild == c)
{
cd[--start] = '0';
}
else
{
cd[--start] = '1';
}
}
m_HC[i].pstring = new char[m_HCsize-start];
cout<<"第"<<i<<"个字符"<<ht.m_HT[i].ch<<"的编码是：";
for (j = start; j < m_HCsize; j++)
{
cout<<cd[j];
m_HC[i].pstring[j-start] = cd[j];
}
cout<<endl;
}
}
//对用字符串组成的电文用赫夫曼编码表进行编码
void HuffmanCoder::Coder(char ch[])
{
ofstream outfile("f1.dat",ios::out);
for (int i = 0; i < strlen(ch); i++)
{
for (int j = 0; j < m_HCsize; j++)
{
if (m_HC[j].ch == ch[i])
{
for (int k = 0; m_HC[j].pstring[k];k++)
{
cout<<m_HC[j].pstring[k];
outfile.put(m_HC[j].pstring[k]);
}
break;
}
}
}
cout<<endl;
outfile.close(); //关闭数据文件
}
//对用0,1组成的电文用赫夫曼树进行译码
void HuffmanCoder::Decoder(HuffmanTree& ht)
{
char ch[256];
int j = 0, i = 0, p, pre, root = ht.m_HTsize - 1;
ifstream infile("f1.dat",ios::in);
while (infile.get(ch[j]))
{
j++;
}
ch[j] = 0;
cout<<"需译制的二进制电文是："<<endl;
cout<<ch<<endl;
cout<<"译码结果："<<endl;
pre = -1;
p = root;
while (i < strlen(ch))
{
while(p != -1)
{
if (ch[i] == '0')
{
pre = p;
p = ht.m_HT[p].lchild;
}
else
{
pre = p;
p = ht.m_HT[p].rchild;
}
i++;
}
cout<<ht.m_HT[pre].ch;
i--;
pre = -1;
p = root;
}
cout<<endl;
infile.close();
}主函数如下：
//main.cpp
#include <iostream>
#include <fstream>
#include "HuffmanCoder.h"
using namespace std;
void main(int argc, char* argv[])
{
ifstream cin("input.txt");
int n;
cout<<"---此程序实现建立赫夫曼树并求赫夫曼编码---"<<endl<<endl;
cout<<"请输入树叶结点的个数(n>1)：";
cin>>n;
char chA[256];
int WeightA[256];
for (int i = 0; i < n; i++)
{
cout<<"请输入第"<<i<<"个字符及其权值"<<endl;
cin>>chA[i]>>WeightA[i];
}
HuffmanTree ht(n,chA,WeightA);
ht.Display();
HuffmanCoder hc(n);
hc.CreateBook(ht);
cout<<"请输入需编码的字符串（字符串中的字符必须是当前对象中的字符）："<<endl;
cin>>chA;
cout<<"编码结果"<<endl;
hc.Coder(chA);
cout<<endl;
hc.Decoder(ht);
cout<<endl;
system("pause");
}
程序输入：
程序输出：
