题目描述
在掌握赫夫曼树构建的基础上，实现赫夫曼解码
赫夫曼构建中，默认左孩子权值不大于右孩子权值
如果遇到两个孩子权值相等，那么按输入顺序或生成顺序来排列。
例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子
例如有两个叶子权值都是4，那么按输入顺序，先输入权值的叶子是左孩子
请完成以下程序填空
输入
第一行输入n，表示有n个叶子
第二行输入n个叶子权值，权值全是正整数
第三行输入n个叶子对应的字符，权值全是正整数
第四行输入k，表示要输入k个编码串
接着输入k个编码串
输出
输出k行，每行输出一个编码串的解码结果。
如果编码串非法，则对应的一行输出error，不输出已解码的字符
输入样例1
5 15 4 4 3 2 K G C M W 2 11011010000001 0000011100010
输出样例1
KKCGWM error
思路分析
遍历编码，从树的根节点开始找，如果当前字符是0，判断是否有左孩子，有的话，更新节点为左孩子节点，如果没有，退出输出error。如果当前字符是1，判断是否有有孩子，有的话，更新节点为右孩子节点，如果没有，退出输出error。
如果左右孩子都为0，说明到达叶子节点，尾部添加解码信息。
注意string类对象可直接通过 =实现尾部添加字符（串）。
AC代码
代码语言：javascript复制HuffMan::HuffMan(int n, int *w,char c[]) {
lnum = n;
len = lnum * 2 - 1;
HuffTree = new HuffNode[len 1];
for (int i = 1; i <= lnum; i ) {
HuffTree[i].weight = w[i-1];
HuffTree[i].letter=c[i-1];
HuffTree[i].parent = HuffTree[i].lchild = HuffTree[i].rchild = 0;
}
for (int i = lnum 1; i <= len; i )
HuffTree[i].weight = HuffTree[i].parent = HuffTree[i].lchild = HuffTree[i].rchild = 0;
}
void HuffMan::buildTree() {
int a, b;
for (int i = lnum 1; i <= len; i ) {
selectMin(i-1, a, b);
HuffTree[a].parent = HuffTree[b].parent = i;
HuffTree[i].lchild = a;
HuffTree[i].rchild = b;
HuffTree[i].weight = HuffTree[a].weight HuffTree[b].weight;
}
}
void HuffMan::selectMin(int n, int &x1, int &x2) {
x1=x2=0;
for (int i =1; i <= n; i )
if (HuffTree[i].parent == 0) {
if(x1==0)
x1=i;
else if(x2==0)
x2=i;
if (HuffTree[i].weight < HuffTree[x1].weight) {
x2 = x1;
x1 = i;
} else if (x2 != 0 && HuffTree[i].weight < HuffTree[x2].weight)
x2 = i;
}
}
void HuffMan::Decoding(std::string cs) {
int j=len;
string temp;
for (int i = 0;cs[i]; i ) {
if(cs[i]=='0'){
if(HuffTree[j].lchild)
j=HuffTree[j].lchild;
else{
cout<<"error"<<endl;
return;
}
}else{
if(HuffTree[j].rchild)
j=HuffTree[j].rchild;
else{
cout<<"error"<<endl;
return;
}
}
if (HuffTree[j].lchild == 0 && HuffTree[j].rchild == 0) {
temp =HuffTree[j].letter;
j = len;
}
}
if(j==len)
cout<<temp<<endl;
else
cout<<"error"<<endl;
}
HuffMan::~HuffMan() {
if (HuffTree)
delete[]HuffTree;
}
