来者可追，往之不谏

努力提升自己

0%

哈夫曼树

发表于 分类于
本文字数： 3.5k 阅读时长 ≈ 6 分钟

哈夫曼树类，实现了哈夫曼树的构造和哈夫曼编码的功能

哈夫曼树

首先定义一个哈夫曼结点的数据结构

1
2
3
4
5
6
7
8
//定义哈夫曼结点
template<class T>
struct HFN {
	T weight;//存放结点权值
	int left=-1;//记录左孩子下标
	int right=-1;//记录右孩子下标
	int parent=-1;//记录父节点下标
};

再次基础上设计好哈夫曼树的类

包含哈夫曼树的构建和编码两个核心功能

用一个vector容器记录结点表，map容器记录编码结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
class Huffman {
public:
	Huffman(const vector<T>& data);//构造哈夫曼树
	void getMin(int& min1, int& min2, int end);//求取权值最小的两个结点,end为结束截止下标(开区间)
	void showHFT();//打印哈夫曼树
	void HuffmanCode(char _left,char _right);//哈夫曼编码,_left,_right左右子树编码
	void backTrack(char _left,char _right,int start);
	void ShowCode();//打印哈夫曼编码
private:
	vector<HFN<T>> HFT;//结点表
	int node_size;//记录原始结点个数
	T MAX;//记录该数据类型最大数值
	string path;//记录回溯过程中的哈夫曼编码
	map<int, string> code;//记录结点的哈夫曼编码
};

哈夫曼树的构建

哈夫曼树的构建需要比较结点的权值。每次将两个权值最小的结点合并在一起。所以需要先写一个取待选列表权值最小的两个结点的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Huffman<T>::getMin(int& min1, int& min2, int end) {
	T minD1 = MAX;
	T minD2 = MAX;
	for (int i = 0;i <end;i++) {
		//检索区间内所有没有父结点的结点
		if (HFT[i].parent == -1) {
			if (minD1 > HFT[i].weight) {
				minD2 = minD1;
				min2 = min1;
				minD1 = HFT[i].weight;
				min1 = i;
			}
			else {
				if (minD2 > HFT[i].weight) {
					minD2 = HFT[i].weight;
					min2 = i;
				}
			}
		}
	}
}

于是，构造哈夫曼树的代码呼之欲出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template<class T>
Huffman<T>::Huffman(const vector<T>& data) {
	node_size = data.size();
	//仅支持int,float,double;更多类型待添加
	//模板类型为int
	if (typeid(T) == typeid(int)) {
		MAX = INT_MAX;
	}
	//模板类型为float
	else if (typeid(T) == typeid(float)) {
		MAX = FLT_MAX;
	}
	//模板类型为double
	else if (typeid(T) == typeid(double)) {
		MAX = DBL_MAX;
	}
	else {
		cerr << "不支持该数据类型!" << endl;
		return;
	}
	//data为数据对，first为键值，second为权重
	vector<T>nodes = data;
	//计算哈夫曼树存储所需的空间大小
	int size = 2 * nodes.size() - 1;
	HFT.resize(size);
	//将数据结点填入哈夫曼树
	int i = 0;
	for (;i < nodes.size();i++) {
		HFT[i].weight = nodes[i];
	}
	//哈夫曼树
	for (;i < size;i++) {
		int index1 = -1, index2 = -1;
		getMin(index1, index2, i);
		HFT[i].weight = HFT[index1].weight + HFT[index2].weight;
		HFT[i].left = index1;
		HFT[i].right = index2;
		HFT[index1].parent = i;
		HFT[index2].parent = i;
	}
}

最后，写一个打印哈夫曼树的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
void Huffman<T>::showHFT()
{
	cout << "index  weight  parent  LTree  RTree" << endl;
	cout << left;     //左对齐输出
	int m = HFT.size();
	for (int i = 0; i < m; i++) {
		cout << setw(5) << i << "  ";                       
		cout << setw(6) << HFT[i].weight << "  ";     
		cout << setw(6) << HFT[i].parent << "  ";
		cout << setw(6) << HFT[i].left << "  ";
		cout << setw(6) << HFT[i].right << "  " << endl;
	}
}

哈夫曼编码

我写的这个哈夫曼编码用到回溯的思想。首先找到根结点，根据构造哈夫曼树的思路，可以比较清楚的得出根节点为最后添加的结点，即哈夫曼结点表中的最后一个元素。得出根节点，从根结点开始左右遍历即可，遍历到左边将左子树编码加入到path容器中，回溯完成后删除path容器中的最后字符；遍历右边同理。

回溯算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
void Huffman<T>::backTrack(char _left, char _right, int start) {
	if (start == -1)return;
	if (start < node_size) {
		code[start] = path;
		return;
	}
	path+= _left;
	backTrack(_left, _right, HFT[start].left);
	path.pop_back();
	path+= _right;
	backTrack(_left, _right, HFT[start].right);
	path.pop_back();

}

哈夫曼编码代码实现

1
2
3
4
5
template<class T>
void Huffman<T>::HuffmanCode(char _left, char _right) {
	int root = 2*(node_size-1);//根节点下标
	backTrack(_left, _right, root);
}

打印哈夫曼编码

1
2
3
4
5
6
template<class T>
void Huffman<T>::ShowCode() {
	for (auto it : code) {
		cout << it.first << " : " << it.second << endl;
	}
}