A 二叉树删除子树
编写程序对给定二叉树执行若干次删除子树操作，输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。
输入格式:
输入第1行为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m，表示要进行的删除操作次数。接下来m行，每行一个不等于0的整数K，表示要删除以K为根的子树。m不超过100，二叉树结点个数不超过5000。输入数据保证各结点数据值互不相等，且删除子树后二叉树不为空。
输出格式:
输出为m行，每行为一组整数，表示执行删除操作后剩余二叉树的中根序列（中根序列中每个整数后一个空格）。若要删除的子树不在当前二叉树中，则该行输出0（0后无空格）。
输入样例:
1 5 8 0 0 0 6 0 0 3 5 8 6输出样例:
1 6 0 1
#include<iostream> #include<cstring> #include<string> #include<unordered_map> using namespace std; const int N = 1e4; int m; int idx, cnt; bool st[N]; unordered_map<int, int>ma; struct tree { int v; int r, l; int father; }p[N]; int build(int root) { int x; cin>>x; if (x == 0) { return 0; } p[root].v = x; ma[x]=root; p[root].l = build(++idx); p[root].r = build(++idx); return root; } void print(int root) { if (st[root]) { return; } if (root == 0) { return; } print(p[root].l); cout << p[root].v << " "; print(p[root].r); } void Delete(int root) { if (root == 0) { return; } ma[p[root].v] = 0; Delete(p[root].l); Delete(p[root].r); } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); build(++idx); cin >> m; while (m--) { int k; cin >> k; if (!ma[k]) { cout << 0 << endl; } else { st[ma[k]] = true; print(1); cout << endl; Delete(ma[k]); } } }
B 重建二叉树
给定非空二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根序列；如给定的中根和后根序列不合法，则亦能识别。
输入格式:
输入包含多组数据（不超过10组），每组为两行字符串，第一行表示某二叉树的后根序列，第二行表示其中根序列。结点的值均为A-Z的大写字母，故二叉树结点个数不超过26，且保证输入的两个序列都是结点的全排列，但不一定是合法的中根和后根序列。输入保证不是空二叉树。
输出格式:
对于每组数据，如果输入的序列不合法（不是同一棵树的中根序列和后根序列），则输出INVALID；若输入序列合法，输出为两行，第一行为一个整数，表示该二叉树的高度，第二行为一个字符串，表示该二叉树的先根序列。
输入样例1:
CEFDBHGA CBEDFAGH CBEDFAGH CEFDBHGA BCA CAB输出样例1:
3 ABCDEFGH INVALID INVALID
经典先序，后序加中序遍历建树板子，如果有需要可以看看我有关二叉树建树的分享。
这个题外加一个判断是否为一个二叉树。
#include<iostream> #include<cstring> #include<string> using namespace std; const int N = 100; struct tree { char c; int l, r; }p[N]; char s1[N]; char s2[N]; int cnt; int max_h; int m; bool flag = 1; int build(int al, int ar, int bl, int br,int h) { if (al > ar) { return 0; } int root = ar; char cc = s1[ar]; int k = 0; while (s1[ar] != s2[k]) { k++; } int len = k - bl; p[root].c = cc; cnt++; if (max_h < h) { max_h = h; } if (bl + len - 1 < 0) { return 0; } if (cnt >m ) { flag = 0; return 0; } p[root].l = build(al, al + len - 1, bl, bl + len - 1,h+1); p[root].r = build(al + len, ar - 1, bl + len + 1, br,h+1); return root; } void print(int root) { cout << p[root].c; if (p[root].l > 0) { print(p[root].l); } if (p[root].r > 0) { print(p[root].r); } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); while (cin >> s1+1 && cin >> s2+1) { flag = 1; m = strlen(s1+1); cnt = 0; max_h = 0; build(1,m,1,m,0); if (cnt < m||!flag) { cout << "INVALID" << endl; } else { cout << max_h << endl; print(m); cout << endl; } } }
C 最右子表达式
表达式可以对应一个树结构，称为表达式树。其中的叶结点对应表达式中的操作数，非叶结点对应运算符，假定所有运算均为二元运算。根据后缀表达式可以构造出表达式二叉树，方法是：从左向右扫描后缀表达式，每扫描到一个符号就生成一个二叉树结点，该符号作为结点的数据域值；若扫描到的符号是操作数，则将此操作数结点压栈；若扫描到的符号是运算符，则从栈中弹出两个结点，分别作为当前运算符结点的右、左孩子，再将当前运算符结点压栈。表达式扫描完成后，栈顶即为表达式树的根结点。表达式树的后根序列即为后缀表达式。
现给定一个后缀表达式exp，请编写程序求出exp的“最右子表达式”。exp的“最右子表达式”是指从exp对应的表达式树右边看向树，从第0层到最底层所能看到的各结点。例如后缀表达式abcdef+−g+∗−h∗+对应的表达式树如图1所示，其最右子表达式为 +∗h∗+g+f 。
输入格式:
第一行是正整数n，表示后缀表达式的数目，1<n≤100。接下来n行，每行是一个由字母构成的字符串，长度不超过500，表示一个后缀表达式，其中小写字母表示操作数，大写字母表示运算符。所有运算符均为二元运算符。
输出格式:
对每个后缀表达式，输出其“最右子表达式”。
输入样例1:
6 abcdefXYgXZYhZX xyPzwIM abcABdefgCDEF abcMN bcMaN fgCeDdEbcAaBF输出样例1:
XZhZXgXf MIw FEDCg NMc Nac FBacg输入样例2:
6 vesBdtIBU crpNWgaQmGG jhAhRnlCJzU laaKuqBHfzVEJ rngAlKCpwgFIM kcqoDYoDeqiYFDL输出样例1:
UBIt GGma UzClh JEVzq MIFgg LDFYio
这道题主要是按照题目所描述的方式建树，即非递归引入栈建立二叉树。
#include<iostream> #include<cstring> #include<string> #include<stack> using namespace std; const int N = 1010; int n, m; bool st[N]; struct tree { char c; int l, r; int h; }p[N]; int idx; char s[N]; int root; void build() { stack<char> q; stack<int> in; for (int i = 1; i <= n; i++) { char c = s[i]; if (c >= 'a' && c <= 'z') { q.push(c); p[++idx].c = c; in.push(idx); } else { char x = q.top(); q.pop(); char y = q.top(); q.pop(); int a = in.top(); in.pop(); int b = in.top(); in.pop(); p[++idx].c = c; p[idx].r = a; p[idx].l = b; q.push(c); in.push(idx); } } root = in.top(); } void fh(int r,int hh) { p[r].h = hh; if (p[r].l) { fh(p[r].l, hh + 1); } if (p[r].l) { fh(p[r].r, hh + 1); } } void print(int r) { if (!st[p[r].h]) { cout << p[r].c; st[p[r].h] = true; } if (p[r].r) { print(p[r].r); } if (p[r].l) { print(p[r].l); } } void init() { for (int i = 1; i < N; i++) { p[i].c = 0; p[i].l = 0; p[i].r = 0; p[i].h = 0; } root = 0; idx = 0; memset(st, false, sizeof(st)); } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> m; while (m--) { cin >> s + 1; init(); n = strlen(s + 1); build(); fh(root, 0); print(root); cout << endl; } }
D 哈夫曼树
编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。
为确保构建的哈夫曼树唯一，本题做如下限定：
- 选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
- 若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
- 生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。
输入格式:
输入为3行。第1行为一个字符串，包含不超过5000个字符，至少包含两个不同的字符，每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串，表示待译码的哈夫曼编码。
输出格式:
输出第一行为用空格间隔的2个整数，分别为压缩前后文本大小，以字节为单位，一个字符占1字节，8个二进制位占1字节，若压缩后文本不足8位，则按1字节算。输出从第二行开始，每行为1个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出INVALID。
输入样例:
cbaxyyzz 0100 011输出样例:
8 3 c:100 b:101 a:110 x:111 y:00 z:01 zy INVALID
这是本次作业的难题了，但是它本身没有难度，主要是熟练哈夫曼建树的模板（有兴趣的可以看看我关于哈夫曼树建树的分享），再加上对一些优先级的限定，我这里采用的是优先队列，目的是省去比较函数，但是如果不熟练的话自己写一个结构体的比较函数就好了。
#include<bits/stdc++.h> #include<unordered_map> using namespace std; const int N = 5010; typedef pair<int, int>PII; typedef pair<int, char>PLL; string str; string s1, s2; int nu[200]; int idx, cnt; bool st[200]; unordered_map<char, string>ma; priority_queue<PII, vector<PII>, greater<PII>>q; priority_queue < pair<int, PLL>, vector < pair<int, PLL>>, greater<pair<int, PLL>>>qq; struct tree { char c; int num; int l, r; }p[N]; void get_map(int root,string s) { if (p[root].c) { ma[p[root].c] = s; return; } get_map(p[root].l, s + '0'); get_map(p[root].r, s + '1'); } void get_ma(string s) { int r = idx; string ans1 = ""; int root = idx; for (int i = 0;i < s.size();i++) { if (s[i] == '0') { root = p[root].l; } else { root = p[root].r; } if (p[root].c) { ans1 += p[root].c; if (i == s.size() - 1) { cout << ans1 << endl; } root = idx; } else { if (i == s.size() - 1) { cout << "INVALID" << endl; } } } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> str >> s1 >> s2; int n1 = str.size(); for (int i = 0;i < str.size();i++) { char c = str[i]; if (!nu[c]) { p[++idx].c = c; cnt++; } nu[c]++; } for (int i = 1;i <= idx;i++) { char cc = p[i].c; qq.push({ nu[cc],{i,cc} }); } for (int i = 1;i < 200;i++) { if (nu[i]) { for (int j = 1;j <= idx;j++) { if (p[j].c == (char)i) { p[j].num = nu[i]; //cout << p[j].c << " " << p[j].num << endl; q.push({ nu[i],j }); } } } } while (q.size() > 1) { auto x = q.top(); q.pop(); auto y = q.top(); q.pop(); p[++idx].num = p[x.second].num + p[y.second].num; p[idx].l = x.second; p[idx].r = y.second; q.push({ p[idx].num,idx }); //cout << p[idx].num << endl; } get_map(idx, ""); int n2 = 0; for (int i = 0;i < str.size();i++) { int x = ma[str[i]].size(); n2 += x; } if (n2 % 8) { n2 = n2 / 8 + 1; } else { n2 = n2 / 8; } cout << n1 << " "<<n2 << endl; //cout << cnt << endl; while (qq.size()) { auto t = qq.top(); qq.pop(); char cc = t.second.second; cout << cc << ":" << ma[cc] << endl; } get_ma(s1); get_ma(s2); }
E 罪犯帮派
Tabu市的警察局决定结束混乱，因此要采取行动根除城市中的几大帮派。目前的问题是，给出两个罪犯，他们是属于同一帮派么？城市里一共有多少个帮派？假设在Tabu市现有n名罪犯，编号为1到n，给出m条消息表示属于同一帮派的两个罪犯编号。请基于这些不完全的信息帮助警方计算出他们想要的信息。
输入格式:
输入第一行为三个正整数，n、m和q。n为罪犯数；m为给出的已知信息数量；q为查询数。接下来m行，每行2个正整数a和b，表示罪犯a和罪犯b属于同一帮派。接下来q行，每行2个正整数c和d，即查询罪犯c和d是否属于同一帮派。每行输入的整数以空格间隔，n、m、q均不超过1000。
输出格式:
输出为q+1行，前q行对应于输入的q个查询的结果，如果属于同一帮派，则输出“In the same gang.”，否则输出“In different gangs.”。最后一行为一个整数，表示帮派数目。
输入样例:
3 2 1 1 2 2 3 1 3输出样例:
In the same gang. 1
并查集没什么好说的。。
#include<iostream> using namespace std; const int N = 1010; int p[N]; int n, m, q; int cnt; int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m >> q; for (int i = 1; i <= n; i++) { p[i] = i; } cnt = n; for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; int x = find(a); int y = find(b); if (x != y) { p[x] = y; cnt--; } } for (int i = 1; i <= n; i++) { p[i] = find(p[i]); } for (int i = 1; i <= q; i++) { int a, b; cin >> a >> b; if (p[a] == p[b]) { cout << "In the same gang." << endl; } else { cout << "In different gangs." << endl; } } cout << cnt; }
F 二叉树路径和II
编写程序找出非空二叉树中和最大的路径，二叉树结点为不等于0的整数。本题的“路径”定义为二叉树中的结点序列vi,...,vj，序列中前一个结点是后一个结点的父结点，但路径不一定是以根结点为起点，也不一定是以叶结点为终点。路径的和定义为该路径所包含的所有结点的数据值之和。
输入格式:
输入为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。
输出格式:
输出为两行，第一行为该二叉树路径和的最大值，第二行为一组整数，每个整数后一个空格，表示该最大路径包含的结点值（按所在层数递增顺序输出）。如果存在多条满足条件的路径，则输出最短（包含结点个数最少）者，如果存在多条最短的路径，则输出最靠左上者。
输入样例1:
1 2 0 0 3 0 0输出样例1:
4 1 3输入样例2:
-1 2 0 0 3 4 0 0 0输出样例2:
7 3 4输入样例3:
3 2 0 0 -1 4 0 0 0输出样例3:
6 3 -1 4
这道题还是有点恶心到我了。。
#include<bits/stdc++.h> using namespace std; const int N = 210; int idx; int max_num=-0x3f3f3f3f; int min_cn=0x3f3f3f3f; int ans[N]; bool flag; struct tree { int v; int l, r; int num; }p[N]; int build(int root) { int val; cin >> val; if (val == 0) { return 0; } p[root].v = val; p[root].l = build(++idx); p[root].r = build(++idx); return root; } void get_maxnum(int root,int num){ if(root==0){ return ; } p[root].num=num+p[root].v; if(p[root].num>max_num){ max_num=p[root].num; } if(p[root].num<=0){ get_maxnum(p[root].l,0); get_maxnum(p[root].r,0); }else{ get_maxnum(p[root].l,p[root].num); get_maxnum(p[root].r,p[root].num); } } void get_mincn(int root,int h1,int h2){ if(root==0){ return; } if(p[root].num==max_num){ min_cn=min(min_cn,h2-h1); } if(p[root].num<=0){ h1=h2+1; } get_mincn(p[root].l,h1,h2+1); get_mincn(p[root].r,h1,h2+1); } void print(int root,int h1,int h2){ if(root==0){ return; } ans[h2]=p[root].v; if(p[root].num==max_num&&h2-h1==min_cn){ for(int i=h1;i<=h2;i++){ cout<<ans[i]<<" "; } return ; } if(p[root].num<=0){ h1=h2+1; } print(p[root].l,h1,h2+1); print(p[root].r,h1,h2+1); } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); build(++idx); get_maxnum(1,0); get_mincn(1,0,0); cout<<max_num<<endl; print(1,0,0); }