1. DS二叉树–赫夫曼树的构建与编码（含代码框架）
题目描述
给定n个权值，根据这些权值构造huffman树，并进行huffman编码
参考课本算法，注意数组访问是从位置1开始
要求：赫夫曼的构建中，默认左孩子权值不大于右孩子权值
代码框架参考如下：
输入
第一行输入t，表示有t个测试实例
第二行先输入n，表示第1个实例有n个权值，接着输入n个权值，权值全是小于1万的正整数
依此类推
输出
逐行输出每个权值对应的编码，格式如下：权值-编码
即每行先输出1个权值，再输出一个短划线，再输出对应编码，接着下一行输入下一个权值和编码。
以此类推
输入样例
1
5 15 4 4 3 2
输出样例
15-1
4-010
4-011
3-001
2-000
参考代码
#include <iostream> #include <string> #include <cstring> using namespace std; const int MaxW = 9999; class huffNode //结点定义 { public: int weight; //权值 int parent; //父结点下标 int left; //左下标 int right; //右下标 }; class huffman { private: void maketree(); void selectmin(int pos, int *s1, int *s2); public: int len; //结点数量 int lnum; //叶子数量 huffNode *hufftree; //赫夫曼树，用数组表示 string *huffcode; //赫夫曼编码 void maketree(int n, int wt[]); void coding(); void destroy(); }; void huffman::maketree(int n, int wt[]) { int i; lnum = n; len = 2 * n - 1; hufftree = new huffNode[2 * n]; huffcode = new string[lnum + 1]; for (i = 1; i <= len; i++) hufftree[i].weight = wt[i - 1]; for (i = 1; i <= len; i++) { if (i > n) hufftree[i].weight = 0; hufftree[i].parent = 0; hufftree[i].left = 0; hufftree[i].right = 0; } maketree(); } void huffman::selectmin(int pos, int *s1, int *s2) { int w1, w2, i; w1 = w2 = MaxW; *s1 = *s2 = 0; for (i = 1; i <= pos; i++) { if (hufftree[i].weight < w1 && hufftree[i].parent == 0) { w2 = w1; *s2 = *s1; *s1 = i; w1 = hufftree[i].weight; } else if (hufftree[i].weight < w2 && hufftree[i].parent == 0) { *s2 = i; w2 = hufftree[i].weight; } } } void huffman::maketree() { int i, s1, s2; for (i = lnum + 1; i <= len; i++) { selectmin(i - 1, &s1, &s2); hufftree[s1].parent = i; hufftree[s2].parent = i; hufftree[i].left = s1; hufftree[i].right = s2; hufftree[i].weight = hufftree[s1].weight + hufftree[s2].weight; } } void huffman::destroy() { len = 0; lnum = 0; delete[] hufftree; delete[] huffcode; } void huffman::coding() { char *cd; int i, c, f, start; cd = new char[lnum]; cd[lnum - 1] = '\0'; for (i = 1; i <= lnum; i++) { start = lnum - 1; for (c = i, f = hufftree[i].parent; f != 0; c = f, f = hufftree[f].parent) { if (hufftree[f].left == c) { start--; cd[start] = '0'; } else { start--; cd[start] = '1'; } } //huffcode[i] = new char[lnum-start]; huffcode[i].assign(&cd[start]); } delete[] cd; } int main() { int t, n, i, j; int wt[800]; huffman myhuff; cin >> t; for (i = 0; i < t; i++) { cin >> n; for (j = 0; j < n; j++) cin >> wt[j]; myhuff.maketree(n, wt); myhuff.coding(); for (j = 1; j <= n; j++) { cout << myhuff.hufftree[j].weight << '-'; cout << myhuff.huffcode[j] << endl; } myhuff.destroy(); } return 0; }
2. DS二叉树–赫夫曼树解码（含代码框架）
题目描述
已知赫夫曼编码算法和程序，在此基础上进行赫夫曼解码
在赫夫曼树的类定义中增加了一个公有方法：
int Decode(const string codestr, char txtstr[]);//输入编码串codestr，输出解码串txtstr
该方法如果解码成功则返回1，解码失败则返回-1，本程序增加宏定义ok表示1，error表示-1
解码方法的代码框架如下：
输入
第一行输入t，表示有t个测试实例
第二行先输入n，表示第1个实例有n个权值，接着输入n个权值，权值全是小于1万的正整数
第三行输入n个字母，表示与权值对应的字符
第四行输入k，表示要输入k个编码串
第五行起输入k个编码串
以此类推输入下一个示例
输出
每行输出解码后的字符串，如果解码失败直接输出字符串“error”，不要输出部分解码结果
输入样例
2
5 15 4 4 3 2
A B C D E
3
11111
10100001001
00000101100
4 7 5 2 4
A B C D
3
1010000
111011
111110111
输出样例
AAAAA
ABEAD
error
BBAAA
error
DCD
参考代码
#include <iostream> #include <string> #include <cstring> using namespace std; const int MaxW = 9999; class huffNode //结点定义 { public: int weight; //权值 int parent; //父结点下标 int left; //左下标 char word; int right; //右下标 }; class huffman { private: void maketree(); void selectmin(int pos, int *s1, int *s2); public: int len; //结点数量 int lnum; //叶子数量 huffNode *hufftree; //赫夫曼树，用数组表示 string *huffcode; //赫夫曼编码 void maketree(int n, int wt[],char ct[]); void coding(); void destroy(); bool decode(const string codestr, char txtstr[]); }; void huffman::maketree(int n, int wt[],char ct[]) { int i; lnum = n; len = 2 * n - 1; hufftree = new huffNode[2 * n]; huffcode = new string[lnum + 1]; for (i = 1; i <= len; i++) { hufftree[i].weight = wt[i - 1]; hufftree[i].word = ct[i - 1]; } for (i = 1; i <= len; i++) { if (i > n) hufftree[i].weight = 0; hufftree[i].parent = 0; hufftree[i].left = 0; hufftree[i].right = 0; } maketree(); } void huffman::selectmin(int pos, int *s1, int *s2) { int w1, w2, i; w1 = w2 = MaxW; *s1 = *s2 = 0; for (i = 1; i <= pos; i++) { if (hufftree[i].weight < w1 && hufftree[i].parent == 0) { w2 = w1; *s2 = *s1; *s1 = i; w1 = hufftree[i].weight; } else if (hufftree[i].weight < w2 && hufftree[i].parent == 0) { *s2 = i; w2 = hufftree[i].weight; } } } void huffman::maketree() { int i, s1, s2; for (i = lnum + 1; i <= len; i++) { selectmin(i - 1, &s1, &s2); hufftree[s1].parent = i; hufftree[s2].parent = i; hufftree[i].left = s1; hufftree[i].right = s2; hufftree[i].weight = hufftree[s1].weight + hufftree[s2].weight; } } void huffman::destroy() { len = 0; lnum = 0; delete[] hufftree; delete[] huffcode; } void huffman::coding() { char *cd; int i, c, f, start; cd = new char[lnum]; cd[lnum - 1] = '\0'; for (i = 1; i <= lnum; i++) { start = lnum - 1; for (c = i, f = hufftree[i].parent; f != 0; c = f, f = hufftree[f].parent) { if (hufftree[f].left == c) { start--; cd[start] = '0'; } else { start--; cd[start] = '1'; } } //huffcode[i] = new char[lnum-start]; huffcode[i].assign(&cd[start]); } delete[] cd; } bool huffman::decode(const string codestr, char txtstr[]) { int i, k, c; char ch; c = len; k = 0; for (i = 0; i < codestr.size(); i++) { ch = codestr[i]; if (ch == '0') { c = hufftree[c].left; } else if (ch == '1') { c = hufftree[c].right; } else { return false; } if (!hufftree[c].left && !hufftree[c].right) { txtstr[k] = hufftree[c].word; k++; c = len; } else { ch = '\0'; } } if (ch == '\0') return false; else { txtstr[k] = '\0'; } return true; } int main() { int t, n, i, j; int wt[800]; char ct[800]; huffman myhuff; cin >> t; for (i = 0; i < t; i++) { cin >> n; char txtstr[800]; for (j = 0; j < n; j++) cin >> wt[j]; for (j = 0; j < n; j++) cin >> ct[j]; myhuff.maketree(n, wt, ct); myhuff.coding(); cin >> n; while(n--) { string codestr; cin >> codestr; if(myhuff.decode(codestr,txtstr)) { cout << txtstr << endl; } else { cout << "error" << endl; } } myhuff.destroy(); } return 0; }
3. DS树–带权路径和
题目描述
计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。
已知一棵二叉树的叶子权值，该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数，然后求总和。如下图中，叶子都用大写字母表示，权值对应为：A-7，B-6，C-2，D-3
树的带权路径和 = 71 + 62 + 23 + 33 = 34
输入
第一行输入一个整数t，表示有t个二叉树
第二行输入一棵二叉树的先序遍历结果，空树用字符‘0’表示，注意输入全是英文字母和0，其中大写字母表示叶子
第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应
以此类推输入下一棵二叉树
输出
输出每一棵二叉树的带权路径和
输入样例
2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20
输出样例
34
40
参考代码
#include <iostream> #include <string> using namespace std; class BitreeNode { public: char data; int weight; int height; BitreeNode *left; BitreeNode *right; BitreeNode() { weight = 0; height = 0; left = NULL; right = NULL; } }; class Bitree { public: BitreeNode *Root; int pos, index; ///index控制数组非0权值 string strtree; int API; Bitree(int *w, string str) { pos = index = 0; API = 0; strtree = str; Root = CreateBitree(w, 0); ///根结点无双亲，双亲高度为0 } BitreeNode *CreateBitree(int *w, int fatherheight) { char ch = strtree[pos]; pos++; if (ch == '0') { return NULL; } else { BitreeNode *T = new BitreeNode(); T->data = ch; T->height = fatherheight + 1; if (T->data >= 'A' && T->data <= 'Z') { T->weight = w[index]; index++; } T->left = CreateBitree(w, T->height); T->right = CreateBitree(w, T->height); return T; } } void preorder(BitreeNode *T) { if (T != NULL) { API += T->weight * (T->height - 1); ///高度减1才是对应乘的值 preorder(T->left); preorder(T->right); } return; } }; int main() { int T; cin >> T; while (T--) { string str; cin >> str; int n; cin >> n; int *a = new int[n]; for (int i = 0; i < n; i++) cin >> a[i]; Bitree Tree(a, str); Tree.preorder(Tree.Root); cout << Tree.API << endl; } //system("pause"); return 0; }
