题目

In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”,and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string “aaaxuaxz”, we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}, or in another way as {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}, both compress the string into 14 bits. Another set of code can be given as {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}, but {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} is NOT correct since “aaaxuaxz” and “aazuaxax” can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤63), then followed by a line that contains all the N distinct characters and their frequencies in the following
format:

c[1] f[1] c[2] f[2] … c[N] f[N]

where c[i] is a character chosen from {‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (≤1000), then followed by M student submissions. Each student submission consists of N lines, each in the format:

c[i] code[i]

where c[i] is the i-th character and code[i] is an non-empty string of no more than 63 '0’s and '1’s.

Output Specification:

For each test case, print in each line either “Yes” if the student’s submission is correct, or “No” if not.
Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code
length being optimal is considered correct.

Sample Input:

7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11

Sample Output:

Yes
Yes
No
No

解题思路

1.首先要明白题意，题目中说哈夫曼算法可以得到最优编码，但是最优编码不一定通过哈夫曼算法得到，也就是说最优编码可能不唯一，哈夫曼算法得到的只是其中一种。

2.哈夫曼编码的特点：

1.最优编码——总长度（WPL）最小
2.无歧义解码——前缀码：数据仅存于叶子节点
3.没有度为1的结点——满足前两条一定有第三条：可以用反证法，如果有一个结点的度为1，那么这个结点就不是编码的结点，而这个度为1的结点肯定可以去掉，就不满足1了。

3.要判断提交的哈夫曼编码是否正确，就要判断通过提交的哈夫曼编码建的树是否符合哈夫曼编码的特点1和2。

4.判断特点1或2，都需要建树来检查是否符合，我们通过哈夫曼算法的到最小WPL和建完树的WPL比较。建树这一步，我考虑可不可以通过判断两棵树是否同构来判断是否是最优编码，但是即使不同构也可能是最优编码，所以不能这么判断。

代码：

#include <iostream>
#include <queue>
#include <string>
#include <vector>#define MinData -1
#define MAXSIZE 1001using namespace std;using HuffmanTree =class TreeNode*;
class TreeNode {
private:int Weight=0;   //权重HuffmanTree Left=nullptr;HuffmanTree Right=nullptr;public:friend class MinHeap;int WPL(int Depth);   //用来计算最优编码长度,H是深度bool is_suc_BuildHT(string Code, vector<int> Weight_,int index);    //用来将读入的编码转换成树,判断是否成功
};class MinHeap {
private:HuffmanTree Elements[MAXSIZE];       //存储堆元素的数组int Size;           //堆的当前元素个数int Capacity;      //堆的最大容量,这里是指存入的结点数public:MinHeap(int MaxSize);HuffmanTree Huffman();       //构造哈夫曼树void AddData(vector<int> Weight_);  //先按完全二叉树加入数据HuffmanTree Delete();   //取出堆顶void PercDown(int Root);         //下滤函数void BuildMinHeap();               //按权重调整函数void Insert(HuffmanTree item);     //插入元素 
};int main()
{HuffmanTree T;           //为了求最小WPL而建的树int Num_of_Node, Num_of_test;    //结点数，检查的个数vector<int> Weight;  //存放权重值int CodeLen;    //最优WPLqueue<int> Q;  //用来存放判断的结果  int count = 0;  //为了结尾输出没有换行符cin >> Num_of_Node;       //输入结点数MinHeap H{ Num_of_Node };   //建立堆Hchar c_;int weight_;for (int i = 0; i < Num_of_Node; i++) {    //将权重值读入到数组中cin >> c_ >> weight_;Weight.push_back(weight_);}H.AddData(Weight);   //加入数据，按照完全二叉树H.BuildMinHeap();    //按权值将堆调整为最小堆T=H.Huffman();  //生成哈夫曼树CodeLen = T->WPL(0);  //求最小WPLcin >> Num_of_test;   //读入要测试的数量for (int i = 0; i < Num_of_test; i++) {int flag = 1;char C;string Code;HuffmanTree HT=new TreeNode;   //根据编码构建的树for (int j = 0; j < Num_of_Node; j++) {     //测试编码cin >> C >> Code;if (Code.length() > Num_of_Node - 1) flag = 0;   //长度不符合if (flag && !HT->is_suc_BuildHT(Code, Weight, j)) flag = 0;    //长度符合了就建树}if (flag&& (HT->WPL(0) == CodeLen)) Q.push(true);  //判断树是否建成，建成是否符合前缀码规范，符合了就再判断WPLelse  Q.push(false); //否则直接判断不是delete HT;}while (!Q.empty()) {if (Q.front()) cout << "Yes";else cout << "No";Q.pop();count++;if (count != Num_of_test) cout << endl;}return 0;
}bool TreeNode::is_suc_BuildHT(string Code, vector<int> Weight_, int index) {int i = 0;if (i < Code.length()) {if (Code[i] == '0') {if (Left == nullptr) {HuffmanTree T = new TreeNode;T->Weight = Weight_[index];Left = T;if (Code.length() == 1) return true; }if (Code.length() == 1) return false;else return Left->is_suc_BuildHT(Code.substr(i + 1), Weight_, index);}else if (Code[i] == '1') {if (Right == nullptr) {HuffmanTree T = new TreeNode;T->Weight = Weight_[index];Right = T;if (Code.length() == 1) return true;}if (Code.length() == 1) return false;else return Right->is_suc_BuildHT(Code.substr(i + 1), Weight_, index);}}  
}int TreeNode::WPL(int Depth) {if (Left == nullptr && Right == nullptr)return Depth * Weight;else if (Left && Right) return Left->WPL(Depth + 1) + Right->WPL(Depth + 1);else return -1000;  //在上一步建树的时候，可能会有树不符合哈夫曼树的特点3
}HuffmanTree MinHeap::Huffman(){    //假设H->Capacity个权重值已经存放在H->Element[]->WeightHuffmanTree T;for (int i = 1; i < Capacity; i++){T = new TreeNode;T->Left = Delete();T->Right = Delete();T->Weight = T->Left->Weight + T->Right->Weight;Insert(T);     //将T插入最小堆}T = Delete();return T;
}MinHeap::MinHeap(int MaxSize) {Size = MaxSize;Capacity = MaxSize;HuffmanTree Node = new TreeNode;Node->Weight = MinData;             //定义哨兵为堆中所有元素的最小值Elements[0] = Node;
}void MinHeap::AddData(vector<int> Weight_) {for (int i = 0; i < Capacity; i++) {HuffmanTree Node = new TreeNode;Node->Weight = Weight_[i];Elements[i + 1] = Node;}
}HuffmanTree MinHeap::Delete(){int Parent, child;HuffmanTree MinItem, temp;/*有需要可以插入判断堆是否为空*/MinItem = Elements[1];temp = Elements[Size--];for (Parent = 1; Parent * 2 <= Size; Parent = child){child = Parent * 2;if ((child < Size) && \(Elements[child]->Weight > Elements[child + 1]->Weight))child++;if (temp->Weight <= Elements[child]->Weight) break;elseElements[Parent] = Elements[child];}Elements[Parent] = temp;return MinItem;
}void MinHeap::PercDown(int Root){ /* 下滤：将H中以Elements[p]为根的子堆调整为最小堆 */int Parent, Child;HuffmanTree X;X = Elements[Root]; /* 取出根结点存放的值 */for (Parent = Root; Parent * 2 <= Size; Parent = Child) {Child = Parent * 2;if ((Child != Size) && (Elements[Child]->Weight > Elements[Child + 1]->Weight))Child++;  /* Child指向左右子结点的较小者 */if (X->Weight <= Elements[Child]->Weight) break; /* 找到了合适位置 */else  /* 下滤X */Elements[Parent] = Elements[Child];}Elements[Parent] = X;
}void MinHeap::BuildMinHeap(){ /* 调整Elements[]中的元素，使满足最小堆的有序性  *//* 这里假设所有H->Size个元素已经存在Elements[]中 */int i;/* 从最后一个结点的父节点开始，到根结点1 */for (i = Size / 2; i > 0; i--)PercDown(i);
}void MinHeap::Insert(HuffmanTree item){int i;/*有需要可以判断堆是否已满*/i = ++Size;    //指向堆最后一个元素的位置for (; Elements[i / 2]->Weight > item->Weight; i /= 2) {      //哨兵解决了插入的结点是所有结点最小的情况Elements[i] = Elements[i / 2];}Elements[i] = item;
}

运行结果：