const int N = 1e6 + 10;

// 二叉树的存储,l数组为左节点,r数组为右结点
int l[N], r[N];
// 存储节点的数据
char w[N];
// 节点的下标指针
int idx = 0;

// 先序创建
int pre_create(int n) {
cin >> w[n];
if (w[n] == ‘#’) return -1;
l[n] = pre_create(idx);
r[n] = pre_create(idx);
return n;
}

// 中序创建
int in_create(int n) {
if (w[n] == ‘#’) return -1;
l[n] = in_create(idx);
cin >> w[n];
r[n] = in_create(idx);
return n;
}

// 后序创建
int back_create(int n) {
if (w[n] == ‘#’) return -1;
l[n] = back_create(idx);
r[n] = back_create(idx);
cin >> w[n];
return n;
}

// 先序遍历
void pre_print(int n){
if (w[n] != ‘#’) cout << w[n] << ‘ ‘;
if (l[n] > 0) pre_print(l[n]);
if (r[n] > 0) pre_print(r[n]);
}

// 中序遍历
void in_print(int n){
if (l[n] > 0) in_print(l[n]);
if (w[n] != ‘#’) cout << w[n] << ‘ ‘;
if (r[n] > 0) in_print(r[n]);
}

// 后序遍历
void back_print(int n){
if (l[n] > 0) back_print(l[n]);
if (r[n] > 0) back_print(r[n]);
if (w[n] != ‘#’) cout << w[n] << ‘ ‘;
}

// 层序遍历
void bfs(int root){
queue[HTML_REMOVED] que;
que.push(root);
while (!que.empty()) {
int t = que.front();
cout << w[t] << ‘ ‘;
que.pop();
if (l[t] > 0 && w[l[t]] != ‘#’)
que.push(l[t]);
if (r[t] > 0 && w[r[t]] != ‘#’)
que.push(r[t]);
}
}