@[chair0114](/user/908638)
不同含义尽量使用不同变量。
建议你加上注释。
今天太晚了,明天再教你。
by CleanIce @ 2023-08-26 22:25:21
@[chair0114](/user/908638)
还有一些不必要的类型转换。如从 `char` 到 `int` 是安全的隐式类型转换,不用显示转换,这是因为 `char` 只有 $1$ 字节但 `int` 有 $4$ 字节,从小到大是安全的。
从 `int` 到 `int` 就更不用加了吧?
by CleanIce @ 2023-08-26 22:27:54
@[CleanIce](/user/821660)
存储操作都是算的,可能是后序排列不对,麻烦了QWQ
```cpp
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<cctype>
using namespace std;
int n,s;
int a[1505];
int ch[1500];
struct node{
int x,y;
}q[1500];
void tree_last(int k){
if(q[k].x != 0)tree_last(q[k].x);
if(q[k].y != 0)tree_last(q[k].y);
cout<<(char)ch[k];
}
int main(){
cin>>n;
s = pow(2,n);
for(int i = 1;i <= pow(2,n); ++i){
scanf("%1d",&a[i]);
if(a[i] == 0) ch[s++] = (int) 'B';
else ch[s++] = (int) 'I';
}
s = pow(2,n) * 2 - 1;
for(int i = s;i >= 1; i -= 2){
if(ch[i] == ch[i - 1]) ch[(i + (i - 1)) / 4] = ch[i];
else ch[(i + (i - 1)) / 4] = (int) 'F';
}
s = pow(2,n) - 1;
for(int i = 1;i <= s; ++i){
q[i].x = (int) ch[i * 2];
q[i].y = (int) ch[i * 2 + 1];
}
ch[0] = 0;
//for(int i = 1;i <= 15; ++i) cout<<ch[i]<<endl;结点和叶节点
//for(int i = 1;i <= 7;++i) cout<<q[i].x<<" "<<q[i].y<<endl;左右子树
tree_last(1);
puts(" ");
return 0;
}
```
by chair0114 @ 2023-08-27 07:05:46
@[chair0114](/user/908638)
你的思路有点复杂,实际上更不不需要那么做。
我们可以通过遍历字符串的方式来判断节点的类型。这个用循环即可。然后让每一个节点存储它的类型和左右孩子。
可以使用递归函数解决建树的问题。可以让函数根据字符串创建对应类型的节点,并将该节点的左孩子也使用此函数创建(传入的字符串就是源字符串的左半部分)。同样的方法创建右孩子。
你的后序遍历没有问题。
可以看看我的代码:
```cpp
#include <iostream>
#include <string>
using namespace std;
struct Node { // 用结构体存储节点
char type; // 节点类型
Node* left; // 左孩子
Node* right; // 右孩子
};
char get_type(const string& data); // 根据字符串判断节点类型
Node* make_tree(const string& data); // 建树,返回值为所创建的节点
void show_tree(const Node* root); // 后序遍历输出树
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); // 优化输入输出速度
int _;
cin >> _; // 不需要 n
string data;
cin >> data; // 数据
Node* root = make_tree(data); // 从全部字符串构建。从题中可知,全部字符串代码根节点
show_tree(root); // 后序遍历输出
cout << endl; // 习惯了换行
return 0;
}
char get_type(const string &data) {
bool is_B = true, is_I = true; // 是否是 B 串或 I 串
for (char ch : data) { // 遍历 data 中的所有字符
if (ch == '0') { // 检测到 0
is_I = false; // 不可能为 I
} else if (ch == '1') { // 检测到 1
is_B = false; // 不可能为 B
}
} // is_B 和 is_I 至少一个为 false,至多都为 false,想一想为什么
if (is_I) {
return 'I';
} else if (is_B) {
return 'B';
} else {
return 'F';
}
}
Node* make_tree(const string& data) {
if (data.size() == 1) { // 单个字符
Node *node = new Node(); // 新建节点
node->type = get_type(data);
node->left = node->right = nullptr; // 左右孩子为空
return node; // 返回节点
}
Node *node = new Node();
node->type = get_type(data);
node->left = make_tree(data.substr(0, data.size() / 2)); // 左孩子使用前半个字符串
node->right = make_tree(data.substr(data.size() / 2, data.size() / 2)); // 右孩子使用后半个字符串
return node; // 返回节点
}
void show_tree(const Node *node) {
if (node->left != nullptr) {
show_tree(node->left);
}
if (node->right != nullptr) {
show_tree(node->right);
}
cout.put(node->type); // 输出字符
}
```
没看懂的问我哈。
by CleanIce @ 2023-08-27 19:06:49