哈夫曼树构建、编码、译码C++实现

这里就不仔细讲哈夫曼树的原理了，资料很多，网上和书籍都是有的，主要讲一下如何实现构建哈夫曼树和编码译码的操作！

做这个实验也是花了半天的功夫，等到做完发现其实最难的不是实现，而是难在你要选用什么数据结构去搭建这个哈夫曼树以及编码译码，这个流程下来这个选用的数据结构是很重要的，决定着你的算法是如何的！

我用的是 C++ 实现的，数据结构方面选用了 string、vector、map、二叉链，其实不用 map 也可以，完全可以自己弄个结构体也行的，但是已经学过 STL 表示 C++ 万岁 O(∩_∩)O！

数据结构：Huffman树(哈夫曼树)原理及C++实现

---

哈夫曼树的构造

因为哈夫曼树是一颗满树，每个节点都要存储一些信息，所以我们单独把节点拎出来用结构体表示，也就是下面实现中的 Node 结构体！

struct Node
{
	int _val;
	char _c;
	Node* _left;
	Node* _right;
	Node(int val, char c = '*')
	{
		_val = val;
		_c = c;
		_left = NULL;
		_right = NULL;
		_parent = NULL;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

**为什么这里不用三叉链呢？**因为我们后面其实在实现编码的时候，是通过递归下去的，而译码的时候我们采用的是回溯，但是由于下面我们会有保存根节点，所以我们无需通过三叉链来找双亲，只需要二叉链即可~

接下来是最重要的选择数据结构存储了，首先在选择数据结构来存储的时候，我一开始选择的是两个 vector，一个用来存放出现的字母，一个用来存放根节点。第二个是没毛病的，但是第一个难免在后面编码译码的时候寻找对应的字母的时候，不知道下标是哪个，想了想这不就是哈希表吗，但是 C++11 才有哈希表，所以我最后用了 map 来存储这些字符以及其对应的编码表！（用结构体包装来代替map也行，但是比较费事）

class Huffman
{
private:
	vector<Node*> _v; // 存放根节点
	map<char, string> _s; // 存放哈夫曼编码后每个字符的编码
};
1
2
3
4
5
6

然后就是构建哈夫曼树：

我的思路就是既然每次都要选最优的嘛，也就是最小的，那么我用 vector 来存储这些顶点后，顺便再将其进行排序，采用的是算法库里的 中的 sort，其采用的是快排！

但是有个问题哦，就是 sort 默认是从小到大排序的，但是我的想法是，我们可以从大到小排序，然后每次取最后两个顶点来构建哈夫曼树，然后将这两个顶点尾删掉，要知道 vector 的尾部操作速度可是一流的~

这样子的话我们就得自己搞一个仿函数或者 lambda 表达式，但是 lambda 表达式需要 C++11 才支持（不得不说devC++很鸡肋），仿函数比较的是字符出现的频率：

// 仿函数
struct Compareval
{
	bool operator()(const Node* n1, const Node* n2)
	{
		return n1->_val > n2->_val;
	}
};
1
2
3
4
5
6
7
8

有了仿函数之后我们就能按照顶点的出现频率也就是 _val 来进行排序了！

接下来就是构建哈夫曼树的思路：

• 首先将 countMap 中值进行构造顶点，然后插入到 vector 中，最后进行排序，注意构造节点的时候节点先接收的是 int 然后才是 char
• vector 中现在存放的就是每个单独的节点了，进行循环，每次取 vector 中的后两个节点（因为我们从大到小排序，最后面的是最小的），让他们生成一个新节点 newnode，然后将 newnode 的左右子树变成这两个小的节点（注意这里默认是左小右大），最后将 newnode 插入到 vector 中，重新排序，以此循环，直到 vector 中剩下一个节点，也就是只剩最后的根节点！

// 构建哈夫曼树
// n代表一共出现的字符数量
// countMap存放的是字符和以及出现的次数
Huffman(const int& n, map<char, int>& countMap)
{
    // 将节点按值的大小从大到小存到_v中
    _v.resize(n);
    int i = 0;
    map<char, int>::iterator it = countMap.begin();
    while (it != countMap.end())
    {
        _v[i] = new Node(it->second, it->first);
        ++i;
        ++it;
    }
    std::sort(_v.begin(), _v.end(), Compareval());

    // 构建
    while (_v.size() >= 2)
    {
        // 将新节点左右孩子链接上
        Node* newnode = new Node(_v[_v.size() - 1]->_val + _v[_v.size() - 2]->_val);
        newnode->_left = _v[_v.size() - 1];
        newnode->_right = _v[_v.size() - 2];

        // 将两个已经链接完成的子节点从vector中pop掉
        _v.pop_back();
        _v.pop_back();

        // 将新节点newnode加入到vector中，并重新排序
        _v.push_back(newnode);
        std::sort(_v.begin(), _v.end(), Compareval());
    }

    Inorder(_v[0]);
}

void Inorder(Node* node)
{
    if (node == NULL)
        return;

    Inorder(node->_left);
    cout << node->_c << ":" << node->_val << " ";
    Inorder(node->_right);
}
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
42
43
44
45
46

哈夫曼编码

方法：对树进行遍历，同时记录当前的遍历路径，当我们检索到叶子节点的时候根据其存储字符以及路径编写其对应的编码！

// 哈夫曼树编码
string HuffmanCode(string& txt)
{
    // 通过子函数进行递归完成哈夫曼编码
    huffmancode(_v[0], "");

    // 有了编码表之后，根据原来的字符串txt打印出其哈夫曼编码
    string tmp;
    for (size_t i = 0; i < txt.size(); ++i)
    {
        tmp += _s[txt[i]];
    }
    return tmp;
}

void huffmancode(Node* root, string s)
{
    // 注意递归终止条件
    if (root == NULL)
        return;

    // 如果为叶子节点则将之前累加的字符串s赋给_s中对应字符的编码
    if (root->_left == NULL && root->_right == NULL)
    {
        _s[root->_c] = s;
    }

    // 若不是叶子节点则继续递归，往左就 +'0' ，往右则 +'1'
    huffmancode(root->_left, s + '0');
    huffmancode(root->_right, s + '1');
}
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

哈夫曼解码

解码的话我们将根据编码表来进行，当我们读入一个压缩文本的时候，我们将 从树根处开始遍历 ，若 读入 ‘0’ 我们将遍历其左子树，读入 ‘1’ 遍历其右子树，同时读入文本的下一位。若当前处理的节点为 叶子节点，说明我们已经完成了目前叶子节点字符的编码翻译了，则将当前叶子节点的字符加到 tmp 中，同时 也将压缩文本读入下一位，并 重新回到根节点，以此输出所有储存字符。最后返回 tmp 即可~

// 哈夫曼树解码
string HuffManDecode(string& txt)
{
    string tmp;
    for (size_t i = 0; i < txt.size(); )
    {
        Node* cur = _v[0];

        // 从根开始遍历，直到读到叶子节点
        while (!(cur->_left == NULL && cur->_right == NULL))
        {
            if (txt[i] == '0')
                cur = cur->_left;
            else
                cur = cur->_right;
            ++i;
        }

        tmp += cur->_c;
    }
    return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

完整的代码

#include 
#include 
#include 
#include 
#include 
using namespace std;

struct Node
{
	int _val;
	char _c;
	Node* _left;
	Node* _right;
	Node(int val, char c = '*')
	{
		_val = val;
		_c = c;
		_left = NULL;
		_right = NULL;
	}
};

// 仿函数
struct Compareval
{
	bool operator()(const Node* n1, const Node* n2)
	{
		return n1->_val > n2->_val;
	}
};

class Huffman
{
public:
	// 构建哈夫曼树
	Huffman(const int& n, map<char, int>& countMap)
	{
		// 将节点按值的大小从大到小存到_v中
		_v.resize(n);
		int i = 0;
		map<char, int>::iterator it = countMap.begin();
		while (it != countMap.end())
		{
			_v[i] = new Node(it->second, it->first);
			++i;
			++it;
		}
		std::sort(_v.begin(), _v.end(), Compareval());

		// 构建
		while (_v.size() >= 2)
		{
			// 将新节点左右孩子链接上
			Node* newnode = new Node(_v[_v.size() - 1]->_val + _v[_v.size() - 2]->_val);
			newnode->_left = _v[_v.size() - 1];
			newnode->_right = _v[_v.size() - 2];

			// 将两个已经链接完成的子节点从vector中pop掉
			_v.pop_back();
			_v.pop_back();

			// 将新节点newnode加入到vector中，并重新排序
			_v.push_back(newnode);
			std::sort(_v.begin(), _v.end(), Compareval());
		}

		Inorder(_v[0]);
	}

	// 哈夫曼树编码
	string HuffmanCode(string& txt)
	{
		// 进行哈夫曼编码
		huffmancode(_v[0], "");

		string tmp;
		// 根据原来的字符串txt打印出其哈夫曼编码
		for (size_t i = 0; i < txt.size(); ++i)
		{
			tmp += _s[txt[i]];
		}
		return tmp;
	}

	void huffmancode(Node* root, string s)
	{
		if (root == NULL)
			return;

		if (root->_left == NULL && root->_right == NULL)
		{
			_s[root->_c] = s;
		}

		huffmancode(root->_left, s + '0');
		huffmancode(root->_right, s + '1');
	}

	// 哈夫曼树解码
	string HuffManDecode(string& txt)
	{
		string tmp;
		for (size_t i = 0; i < txt.size(); )
		{
			Node* cur = _v[0];

			// 从根开始遍历，直到读到叶子节点
			while (!(cur->_left == NULL && cur->_right == NULL))
			{
				if (txt[i] == '0')
					cur = cur->_left;
				else
					cur = cur->_right;
				++i;
			}

			tmp += cur->_c;
		}
		return tmp;
	}

    void Inorder(Node* node)
    {
        if (node == NULL)
            return;

        Inorder(node->_left);
        cout << node->_c << ":" << node->_val << " ";
        Inorder(node->_right);
    }
	
private:
	vector<Node*> _v; // 存放根节点
	map<char, string> _s; // 存放哈夫曼编码后每个字符的编码
};

void Count(const string& s, int& n, map<char, int>& countMap)
{
	for (size_t i = 0; i < s.size(); ++i)
		countMap[s[i]]++;

	map<char, int>::iterator it = countMap.begin();
	while (it != countMap.end())
	{
		n++;
		cout << it->first << " 出现 " << it->second << " 次" << endl;
		++it;
	}
}
 
int main()
{
	string s;
	getline(cin, s);

	// 统计电文中字符的出现频率 
	int validNum = 0;
	map<char, int> countMap;
	Count(s, validNum, countMap);

	// 创建哈夫曼树 
	Huffman hm(validNum, countMap);
	cout << endl;

	// 打印出对应的哈夫曼树编码
	cout << "哈夫曼编码: " << hm.HuffmanCode(s) << endl;
	cout << "编码长度为：" << hm.HuffmanCode(s).size() << endl;

	// 打印出对应的哈夫曼树编码的解码
	string tmp = hm.HuffmanCode(s);
	cout << "哈夫曼编码的解码：" << hm.HuffManDecode(tmp) << endl;
	return 0;
}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

运行结果：

abaccdaA
A 出现 1 次
a 出现 3 次
b 出现 1 次
c 出现 2 次
d 出现 1 次
a:3 *:8 c:2 *:5 A:1 *:3 d:1 *:2 b:1
哈夫曼编码: 011110101011100110
编码长度为：18
哈夫曼编码的解码：abaccdaA
1
2
3
4
5
6
7
8
9
10