哈夫曼编码

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 //Huffman树的节点类
 7 typedef struct Node
 8 {
 9     char value;               //结点的字符值   
10     int weight;               //结点字符出现的频度
11     Node *lchild, *rchild;     //结点的左右孩子
12 }Node;
13 
14 //自定义排序规则，即以vector中node结点weight值升序排序
15 bool ComNode(Node *p, Node *q)
16 {
17     return p->weight<q->weight;
18 }
19 
20 //构造Huffman树，返回根结点指针
21 Node* BuildHuffmanTree(vector<Node*> vctNode)
22 {
23     while (vctNode.size()>1)                            //vctNode森林中树个数大于1时循环进行合并
24     {
25         sort(vctNode.begin(), vctNode.end(), ComNode);   //依频度高低对森林中的树进行升序排序
26 
27         Node *first = vctNode[0];    //取排完序后vctNode森林中频度最小的树根
28         Node *second = vctNode[1];   //取排完序后vctNode森林中频度第二小的树根
29         Node *merge = new Node;      //合并上面两个树
30         merge->weight = first->weight + second->weight;
31         merge->lchild = first;
32         merge->rchild = second;
33 
34         vector<Node*>::iterator iter;
35         iter = vctNode.erase(vctNode.begin(), vctNode.begin() + 2);    //从vctNode森林中删除上诉频度最小的两个节点first和second
36         vctNode.push_back(merge);                                 //向vctNode森林中添加合并后的merge树
37     }
38     return vctNode[0];            //返回构造好的根节点
39 }
40 
41 //用回溯法来打印编码
42 void PrintHuffman(Node *node, vector<int> vctchar)
43 {
44     if (node->lchild == NULL && node->rchild == NULL)
45     {//若走到叶子节点，则迭代打印vctchar中存的编码
46         cout << node->value << ": ";
47         for (vector<int>::iterator iter = vctchar.begin(); iter != vctchar.end(); iter++)
48             cout << *iter;
49         cout << endl;
50         return;
51     }
52     else
53     {
54         vctchar.push_back(1);     //遇到左子树时给vctchar中加一个1
55         PrintHuffman(node->lchild, vctchar);
56         vctchar.pop_back();       //回溯，删除刚刚加进去的1
57         vctchar.push_back(0);     //遇到左子树时给vctchar中加一个0
58         PrintHuffman(node->rchild, vctchar);
59         vctchar.pop_back();       //回溯，删除刚刚加进去的0
60 
61     }
62 }
63 
64 int main()
65 {
66     cout << "************ Huffman编码问题 ***************" << endl;
67     cout << "请输入要编码的字符,并以空格隔开（个数任意）：" << endl;
68     vector<Node*> vctNode;        //存放Node结点的vector容器vctNode
69     char ch;                      //临时存放控制台输入的字符
70     while ((ch = getchar()) != '
')
71     {
72         if (ch == ' ')continue;      //遇到空格时跳过，即没输入一个字符空一格空格
73         Node *temp = new Node;
74         temp->value = ch;
75         temp->lchild = temp->rchild = NULL;
76         vctNode.push_back(temp);  //将新的节点插入到容器vctNode中
77     }
78 
79     cout << endl << "请输入每个字符对应的频度，并以空格隔开：" << endl;
80     for (int i = 0; i<vctNode.size(); i++)
81         cin >> vctNode[i]->weight;
82 
83     Node *root = BuildHuffmanTree(vctNode);   //构造Huffman树，将返回的树根赋给root
84     vector<int> vctchar;
85     cout << endl << "对应的Huffman编码如下：" << endl;
86     PrintHuffman(root, vctchar);
87 
88     system("pause");
89 }