#include <iostream>
using namespace std;
#include <string>
#define MAXLEAF 30 //最大叶子数
#define MAXNODE 2 * MAXLEAF-1 //最大结点数
#define MAXVALUE 10000 //最大值,用于初始化
#define MAXBIT 100 //编码的长度
typedef struct HuffmanNode /* 结点结构体 */
{
double weight; //权植
int parent; //双亲
int lChild; //左孩子
int rChild; //右孩子
string value; //数据
}HNodeType;
typedef struct HuffmanCode /* 编码结构体 */
{
int bit[MAXBIT]; //存储二进制编码的数组
int start; //编码开始下标
}HCodeType;
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF]; /* 定义一个编码结构体数组,长度为叶子的个数*/
/* 构造哈夫曼树 */
void CreateHuffmanTree(HNodeType HuffNode[MAXNODE], int n)
{
//1、初始化: 权植为0,双亲及左右孩子为-1
for (int i = 0; i < 2 * n - 1; i++)
{
HuffNode[i].weight = 0;
HuffNode[i].parent = -1;
HuffNode[i].lChild = -1;
HuffNode[i].rChild = -1;
}
//2、输入n个叶子结点及其权植
for (int j = 0; j < n; j++)
{
cout << "Please input value and weight of leaf node " << j + 1 << endl;
cin >> HuffNode[j].value;
cin >> HuffNode[j].weight;
}
//3、构造 Huffman 树
for (int i = 0; i<n-1; i++) //n个结点,n-1次合并
{
double m1, m2; /* m1、m2中分别存放两个无父结点且结点权值 最小和次小 的两个结点 */
int x1, x2; /* 分别对应m1和m2的下标值 */
m1 = m2 = MAXVALUE;
x1 = x2 = 0;
//3.1 从叶子结点中找最小和次小权植[这些叶子结点包括合并产生的结点]
for (int j = 0; j < n+i; j++)
{
if (HuffNode[j].parent == -1 && HuffNode[j].weight < m1) //双亲不等于 -1不是叶子结点,不再作比较
{
//比最小还小的值,最小先变次小,再把此值变最小
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weight;
x1 = j;
}
else if (HuffNode[j].parent == -1 && HuffNode[j].weight < m2)
{
//比次小还小的值,直接把此值变次小
m2 = HuffNode[j].weight;
x2 = j;
}
}
//3.2 更新树的信息【相当于填表】
HuffNode[n + i].weight = m1 + m2; //生成的权植 放入下标为n+i的结点中
HuffNode[x1].parent = n + i; //最小权植的双亲 放入生成的权植的下标
HuffNode[x2].parent = n + i; //次小权植的双亲 放入生成的权植的下标
HuffNode[n + i].lChild = x1; //生成的权植左孩子 放入最小的下标
HuffNode[n + i].rChild = x2; //生成的权植右孩子 放入次小的下标
/* 用于测试 */
cout << "x1.weight and x2.weight in round " //round: 一轮
<< i + 1 << "\t"
<< HuffNode[x1].weight << "\t"
<< HuffNode[x2].weight << endl;
}
}
/* 哈夫曼树编码 */
void HuffmanTreeCode(HCodeType HuffCode[MAXLEAF], int n)
{
/* 定义一个临时变量来存放求解编码时的信息 */
HCodeType cb; //cb: common buffer(公共缓冲区)
int i, j, child, parent;
//对n个叶子结点进行编码
for (i = 0; i < n; i++)
{
cb.start = n - 1; //从后向前进行编码
child = i;
parent = HuffNode[child].parent;
while (parent != -1) //不是树根就一直编码
{
//左孩子编号为0
if (HuffNode[parent].lChild == child)
{
cb.bit[cb.start] = 0;
}
else
{
//右孩子编号为1
cb.bit[cb.start] = 1;
}
cb.start--;
child = parent;
parent = HuffNode[child].parent;
}
/* 把叶子结点的编码信息从临时编码cd中复制出来,放入编码结构体数组 */
for (j = cb.start + 1; j < n; j++)
{
HuffCode[i].bit[j] = cb.bit[j];
}
HuffCode[i].start = cb.start;
}
}
/* 哈夫曼树译码 */
void HuffmanTreeDecode(HCodeType HuffCode[MAXLEAF], int n)
{
for (int i = 0; i < n; i++)//叶子结点
{
cout << HuffNode[i].value << "HuffmanTree Decode is: ";
//从前向后进行译码
for (int j = HuffCode[i].start+1; j < n; j++)//译码开始下标
{
cout << HuffCode[i].bit[j];//输出译码
}
cout << endl;
}
}
void test01()
{
int n;
cout << "请输入叶子结点的个数:" << endl;
cin >> n;
CreateHuffmanTree(HuffNode, n);// 构造哈夫曼树
HuffmanTreeCode(HuffCode, n); // 哈夫曼树编码
HuffmanTreeDecode(HuffCode, n);// 哈夫曼树译码
}
int main()
{
test01();
system("pause");
return 0;
}
确定合适的数据结构。[顺序存储,结构体数组]
哈夫曼树中没有度为1的结点,则一棵有n个叶子结点的哈夫曼树共有2n - 1个结点(n - 1次的“合并”,每次产生一个新结点)。
构成哈夫曼树后,编码需从叶子结点出发走一条从叶子到根的路径。
译码需要从根出发走一条从根到叶子的路径。那么对于每个结点而言,需要知道每个结点的权值、双亲、左孩子、右孩子和结点的信息。