哈夫曼树和哈夫曼编码与译码

Huffman树的创建

思想概述

为求得最优二叉树，哈夫曼巧妙地涉及到哈夫曼算法。通过哈夫曼算法可以建立一棵哈夫曼树。现有n个结点，如果岸边每个结点都作为一棵二叉树的根结点，那么这个n个根结点就组成了一个森林。把结点在文件中出现的次数定义为该结点的权值。

1.在森林中取权值最小的两个根结点，合并成一棵二叉树，并生成一个新结点T，作为这两个结点的父亲，T的权值是它的两个子结点的权值之和。与此同时，森林中减少了一棵树。

2.对新森林重复上述操作，直至森林中只有唯一的根结点，最后的根结点便是所求的哈夫曼树的根。

注意：最优二叉树未必唯一，而哈夫曼树可能只是满足条件的所有最优二叉树中的一棵。

Huffman结点

假定哈夫曼树中每个结点的结构为：

/*Huffman结点结构体*/
typedef struct HuffmanNode {
	char INFO;  //信息域
	int Weight;  //权重
	HuffmanNode* LLINK;  //左链接
	HuffmanNode* RLINK;  //右链接
}HuffmanNode;

Huffman树

假定与给定的m个权值结合的结点的地址存在于一维数组H[1:m+1]中，并且该数组按每个结点的Weight域已排序（从小到大）。

如Huffman树结点声明所示，其中H为存储Huffman结点的一维数组（Huffman结点内存储了结点权值Weight），且数组H已排序。

/*Huffman树结构体*/
typedef struct HuffmanTree {
	HuffmanNode** H;  //存储Huffman结点的数组
	int m;  //结点个数
}HuffmanTree;

构建Huffman树 

1.初始化

创建所有结点，把每个结点都作为一棵二叉树的根结点，所有结点组成一个森林 。

2.组合

在森林中选取两个最小的结点，合并成一棵二叉树，并并生成一个新结点T，作为这两个结点的父亲，T的权值是它的两个子结点的权值之和。

3.找位置

找到H数组中合适的位置插入新生成的二叉树，使数组保持递增。

4.循环

循环操作所有结点。

HuffmanTree* CreateHuffmanTree(char data[],int weight[],int n) {
	//初始化
	HuffmanTree* tree = new HuffmanTree;
	tree->m = n;
	//每个结点都作为一棵树的根结点，组成森林
	for (int i = 1; i <= tree->m; i++) {
		tree->H[i] = new HuffmanNode;
		tree->H[i]->INFO = data[i];
		tree->H[i]->Weight = weight[i];
		tree->H[i]->LLINK = NULL;
		tree->H[i]->RLINK = NULL;
	}
	//组合过程
	HuffmanNode* p1, * p2,* p,* t;
	int i, j;
	for (i = 1; i < tree->m; i++) {
		t = new HuffmanNode;
		p1 = tree->H[i];
		p2 = tree->H[i + 1];
		t->LLINK = p1;
		t->RLINK = p2;  //链接左右结点
		t->Weight = p1->Weight + p2->Weight;  //权重等于子结点权重之和
		p = t;
		j = i + 2;  //从下一棵结点开始比较
		if (j <= tree->m && p->Weight >= tree->H[j]->Weight) {  //寻找合适的位置，使森林保持递增
			tree->H[j - 1] = tree->H[j];  //小的结点前移，给p结点腾位置
			j++;
		}
		tree->H[j - 1] = p;
	}
	return tree;
}

Huffman编码 

对于所有的编码，哈夫曼编码是文件的总编码长度最短，字符集中的字符所在的结点均是哈夫曼树中的外结点。

将哈夫曼树每个分支结点的左分支标上0，右分支标上1，把从根结点到每个叶结点的路径上的标号连接起来，作为该叶结点所代表的字符的编码。

/*Huffman编码*/
#include <unordered_map>
#include <cstring>
//使用unordered_map,char标志字符，string对应的Huffman编码
typedef unordered_map<char, string> UMCS;
UMCS HuffmanCode;  //Huffman编码
void CreateHuffmanCode(HuffmanNode* t,string code) {
	if (t == NULL) return;
	//左右子结点为空，则为叶结点，为字符
	if (t->LLINK == NULL && t->RLINK == NULL) {
		HuffmanCode[t->INFO] = code;
	}
	//递归处理左右结点，进行Huffman编码
	CreateHuffmanCode(t->LLINK, code + "0");  //左结点，+"0"
	CreateHuffmanCode(t->RLINK, code + "1");  //右结点，+"1"
}

Huffman译码

对压缩后的数据文件进行解码的过程是，依次读入文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向其左儿子，否则走向其右儿子，到达某一叶结点时，便可以译出相应的字符。

/*Huffman译码*/
void TransHuffmanCode(HuffmanNode* root) {
	HuffmanNode* t=root;
	string ans="";  //存储最终译码结果
	string code;  
	cin >> code;  //读入二进制Huffman编码
	int n = code.size();  //二进制编码的长度
	for (int i = 0; i < n; i++) {
		char ch = code[i];  
		if (ch == '0') t = t->LLINK;  //读入'0'，则走左分支
		if (ch == '1') t = t->RLINK;  //读入'1'，则走右分支
		//若走到叶结点，当前阶段译码成功，可存入一个字符
		if (t->LLINK == NULL && t->RLINK == NULL) {  
			ans = ans + t->INFO;  //串入译码结果
			if (i != n - 1) t = root;  //若此时还剩二进制编码未译，回到根结点，继续译码
		}
		
	}
	//若二进制编码读入完全，此时却没有走到叶结点，证明译码不完全，译码错误
	if (!(t->LLINK == NULL && t->RLINK == NULL))
		cout << "INVALID" << endl;  //译码错误，输出"INVALID"
	else
		cout << ans<<endl;  //译码成功，输出最终译码结果
}

《数据结构》刘大友||第5章 树与二叉树||5.4压缩与哈夫曼树