哈夫曼树 哈夫曼编码 （C++）

原理

哈夫曼树原理
原理上述文章讲的比较清楚，本文的code也参考了该篇博客。
在其基础上，采用c++进行实现，利用map设计了编码和解码的功能，更加直观。

完整程序

Huffmantree.h

#pragma once
#include <vector>
#include <iostream>
#include <string>
#include <map>
#define MAX 9999
using namespace std;
//创建哈夫曼树的节点结构体
typedef struct {
	int LChild;//左孩子索引
	int RChild;//右孩子索引
	int Parent;//父母索引
	int Weight;//权重（字符出现的次数）
}HT_Node;
//建立哈夫曼树的类
class Huffmantree
{
public:
	map<char, int> map_weight;//保存字符和其权重的map(key:字符 value:权重)
	map<char, string> map_encoder;//保存字符和其哈夫曼编码的map(key:字符 value:哈夫曼编码)
	map<string, char> map_decoder;//保存哈夫曼编码和其对于字符的map(key:哈夫曼编码 value:字符)
	vector<HT_Node> HT;//将哈夫曼树的节点都保存到一个vector中
	string str;//用来进行哈夫曼树建立的字符串
	int num;//不重复字符的总数量
	Huffmantree(string str);//构造函数
	void select(int n, int* minIndex1, int* minIndex2);//工具函数：找到节点vecotor中最小权重的两个节点
	void CreatHT();//创建哈夫曼树
	void HT_Encode_display();//显示哈夫曼编码
	void HT_Encoder(string str);//利用上述编码对str进行编码（注意：所采用的字符必须属于上述编码中的字符）
	void HT_Decoder(string str);//利用上述编码对str进行解码
};

Huffmantree.cpp

#include "Huffmantree.h"
#include <algorithm>
Huffmantree::Huffmantree(string str)//构造函数：初始化str属性
{	
	this->str = str;
}
//工具函数：把HT(哈夫曼节点vector)中的两个最小权重的节点索引提取 n为提取范围（HT[0]-HT[n]),minIndex1,2为索引
void Huffmantree::select(int n,int* minIndex1, int* minIndex2)
{
	
	*minIndex1 = -1;
	*minIndex2 = -1;
	int min1 = MAX;int min2 = MAX;
	for (int i = 0; i < n; i++) {
		if (HT[i].Parent == -1) {
			if (HT[i].Weight < min1) {
				*minIndex2 = *minIndex1;
				min2 = min1;
				*minIndex1 = i;
				min1 = HT[i].Weight;
			}
			else if (HT[i].Weight < min2) {
				*minIndex2 = i;
				min2 = HT[i].Weight;
			}
		}

	}
	
}
//创建哈夫曼树
void Huffmantree::CreatHT()
{
	//首先获取权重，存储在中map_weight
	int len = 0;
	for (int i = 0; i < this->str.length(); i++) {
		if (this->map_weight.count(this->str[i]) == 0) {
			len++;
			this->map_weight[this->str[i]] = 0;
			for (int j = i; j < this->str.length(); j++) {
				if (this->str[i] == this->str[j]) {
					this->map_weight[this->str[i]] = this->map_weight[this->str[i]] + 1;
				}
			}
		}
	}
	//获取不重复字符数的最大数量num
	this->num = len;
	//初始化叶子节点（叶子节点存储在0-n-1的位置）
	HT_Node node;
	for (map<char,int>::iterator iter=this->map_weight.begin(); iter!=this->map_weight.end(); iter++) {
		node.LChild = -1;
		node.RChild = -1;
		node.Parent = -1;
		node.Weight = iter->second;
		HT.push_back(node);
	}
	//初始化非叶子节点（非叶子节点存储在n到2*n-1的位置）
	for (int i = len; i < 2 * len - 1; i++) {
		node.LChild = -1;
		node.RChild = -1;
		node.Parent = -1;
		node.Weight = 0;
		HT.push_back(node);
	}
	//建立哈夫曼树
	int minIndex1, minIndex2;
	for (int i = len; i < 2 * len - 1; i++) {
		this->select(i, &minIndex1, &minIndex2);
		this->HT[i].Weight = this->HT[minIndex1].Weight + this->HT[minIndex2].Weight;
		this->HT[i].LChild = minIndex1;
		this->HT[i].RChild = minIndex2;
		this->HT[minIndex1].Parent = i;
		this->HT[minIndex2].Parent = i;

	}
	//获取哈夫曼编码
	int i = 0;
	for (map<char, int>::iterator iter = this->map_weight.begin(); iter!=this->map_weight.end();iter++) {
		string str_encode;//存储编码
		int parent_index = HT[i].Parent;
		int curent_index = i;
		while (parent_index != -1) {//从叶子节点倒推到根节点来获取编码
			HT_Node parent_node = HT[parent_index];
			if (parent_node.LChild == curent_index) {//如果在左子树 则编码为0
				str_encode += '0';
			}
			else if (parent_node.RChild == curent_index) {//如果在右子树 则编码为1
				str_encode += '1';
			}
			curent_index = parent_index;
			parent_index = HT[parent_index].Parent;
		}
		reverse(str_encode.begin(), str_encode.end());//因为是从叶子节点到根节点，属于倒退，所以编码需要反转一下
		//将编码情况存储在编码和解码的map中，使得字符和其编码可以互相索引
		this->map_encoder[iter->first] = str_encode;
		this->map_decoder[str_encode] = iter->first;
		i++;
	}


}

void Huffmantree::HT_Encode_display()//打印编码
{
	for (map<char, string>::iterator iter = this->map_encoder.begin(); iter != this->map_encoder.end(); iter++) {
		cout << iter->first << " 的编码为： " << iter->second << endl;
	}
}

void Huffmantree::HT_Encoder(string str)//根据所得编码对字符串编码
{
	string str_encoder;
	for (int i = 0; i < str.length(); i++) {
		str_encoder += this->map_encoder[str[i]];
	}
	cout <<str<< " 的编码为： "<<str_encoder << endl;
}

void Huffmantree::HT_Decoder(string str)//根据所得编码对字符串解码
{
	string str_decoder;
	string tmp;//因为解码是多个字符对应一个解码字符，所以需要累加字符，直到匹配到编码
	for (int i = 0; i < str.length(); i++) {
		tmp += str[i];
		if (this->map_decoder.count(tmp) == 1) {
			str_decoder += this->map_decoder[tmp];
			tmp="";
		}

	}
	cout << str << " 的解码为： " << str_decoder << endl;
}

main.cpp

#include <iostream>
#include <string>
#include "Huffmantree.h"
using namespace std;
int main() {
	string str="i love you i miss you i fuck you i kill you";
	Huffmantree HT(str);
	HT.CreatHT();//创建哈夫曼树
	HT.HT_Encode_display();//显示哈夫曼编码结果
	HT.HT_Encoder("i love you");//编码字符串
	HT.HT_Decoder("011000100001011101");//解码字符串
}