介绍
又称最优树，是一类带权路径长度最短的树，在实际生活有着广泛的应用。
构造
-
构造过程
- 给定n个权值{w1,w2,…,wn}，构造n棵只有根节点的二叉树，这n棵二叉树构成森林F。
- 在森林F中选取两棵根节点的权值最小的树（构造的新树也算，若权值最小是新树之外的两颗，那就重新再组有课树）作为左右子树构造新的二叉树，且其根节点权值为左右孩子权值和。
- 在森林F中删去这两棵树，同时加入新的树。
- 重复2、3直到F只含一棵树为止。
-
构造算法
#include<iostream> using namespace std; /* 树节点结构：权值weight+父母parent+左孩子lchild+右孩子rchild 存储在大小为2n-1(n个节点构成的哈夫曼树有2n-1个节点)的数组内，但是为了方便，0不使用，从1开始，所以数组大小要定义为2n，通过下标去调用 */ typedef struct { int weight;//权值 int parent, lchild, rchild;//对应下标 }HTNode, * HuffmanTree; //HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置 void Select(HuffmanTree HT, int end, int& s1, int& s2) { int min1, min2; //遍历数组初始下标为 1 int i = 1; //找到还没构建树的结点 while (HT[i].parent != 0 && i <= end) { i++; } min1 = HT[i].weight; s1 = i; i++; while (HT[i].parent != 0 && i <= end) { i++; } //对找到的两个结点比较大小，min2为大的，min1为小的 if (HT[i].weight < min1) { min2 = min1; s2 = s1; min1 = HT[i].weight; s1 = i; } else { min2 = HT[i].weight; s2 = i; } //两个结点和后续的所有未构建成树的结点做比较 for (int j = i + 1; j <= end; j++) { //如果有父结点，直接跳过，进行下一个 if (HT[j].parent != 0) { continue; } //如果比最小的还小，将min2=min1，min1赋值新的结点的下标 if (HT[j].weight < min1) { min2 = min1; min1 = HT[j].weight; s2 = s1; s1 = j; } //如果介于两者之间，min2赋值为新的结点的位置下标 else if (HT[j].weight >= min1 && HT[j].weight < min2) { min2 = HT[j].weight; s2 = j; } } } /* 算法步骤 1.初始化 ·申请大小2n的动态数组，从1开始循环到2n-1，把所有节点的父母、孩子都设为0 ·循环n次（1-n），输入n个叶子节点的权值 2.创建树 ·循环n-1次（n+1~2n）的选择、删除与合并来创建哈夫曼树 ·选择：从当前森林选出双亲为0且权值最小的节点的下标s1和s2 ·删除：把s1和s2的父母改为非0，即当前的下标 ·合并：把s1和s2的权值相加，成为当前节点的权值，同时记录左右孩子下标，即s1和s2 */ void CreateHuffmanTree(HuffmanTree& HT, int n) { if (n <= 1) return;//检测输入是否正确 /*--------------------------------------------初始化--------------------------------------------------------*/ int m = 2 * n - 1;//n个叶子节点构建的树有2n-1个节点 HT = new HTNode[m + 1];//从1开始，故加一 for (int i = 1; i <= m; i++) {//全部置0 HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; } for (int i = 1; i < n; i++) {//输入权值 cin >> HT[i].weight; } /*-------------------------------------------构造哈夫曼树----------------------------------------------------*/ for (int i = n + 1; i <= m; i++) { int s1, s2; Select(HT, i - 1, s1, s2);//选择函数 HT[i].lchild = s1;//当前节点左孩子设置为s1 HT[i].rchild = s2;//当前节点右孩子设置为s2 HT[s1].parent = HT[s2].parent = i;//s1、s2父母设置为当前节点下标 HT[i].weight = HT[s1].weight + HT[s2].weight;//当前节点权值为s1和s2总和 } }
编码
进行数据压缩时，为了使压缩后的数据文件尽可能短，可采用不定长编码。为了正确编码，用哈夫曼树来实现。
关于编码，有两个概念：
- 前缀编码：在一个编码方案里，任一个编码都不是其他任何编码的前缀（最左子串），则为前缀编码。（不懂百度一下）
- 哈夫曼编码：约定左支为0，右支为1，则根节点到每个叶子节点路径上的0、1序列就是对应编码。以下是哈夫曼编码的性质
- 哈夫曼编码是前缀编码
- 哈夫曼编码是最优前缀编码
/*
哈夫曼编码表存储结构
因为每个编码不等长，所以定义一个二维字符数组来存储
为了方便，数组下标从1开始使用，故为n+1行
因为事先不能确定编码长度，为了不浪费内存空间，定义一个一维字符数组（长度为n，编码一定不会大于n）来存储后再移入编码表里。值得注意的是，因为哈夫曼编码是从根到叶，而记入cd时是从叶到根，所以需要我们记入cd时要反过来记入
*/
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
/*
算法步骤
1.分配存储n个字符编码的编码表空间HC，长度为n+1
2.分配临时编码存储数组cd，长度为n，cd[n-1]置为‘\0’
3.逐个字符求编码，循环n次，执行以下操作
·设置start用于记录编码在cd中存放的位置，初始化指向最后
·设置变量c用于记录从叶子向上回溯到根节点所经过的节点下标，c初始化为等待编码字符的下标i
·设置变量f用于记录i双亲节点的下标
4.从叶子向上回溯到根节点，当没有回溯到根节点，循环执行以下操作
·回溯一次start向前指一个位置，即--start
·若节点c是f的左孩子，生成0；否则生成1，保存在cd中
·继续回溯，改变c和f的值
5.分配HC空间，记入编码
*/
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{
HC = new char* [n + 1];
char* cd = new char[n];
cd[n - 1] = '\0';
for (int i = 1; i <= n; i++)
{
//前期准备
int start = n - 1;
int c = i;
int f = HT[i].parent;
//开始编码
while (f != 0)//没有到根节点，哈夫曼树只有根节点是无双亲的
{
--start;
if (HT[f].lchild = c)cd[start] = '0';
else cd[start] = '1';
c = f;
f = HT[f].parent;
}
//记入HC
HC[i] = new char[n - start];
strcpy(HC[i], &cd[start]);//记得include<string>
}
delete cd;//释放临时空间
}