题目大意
给出一棵树，让你输出中缀表达式。但是要符合括号格式。
思路解析
既然是中缀表达式妥妥的中序遍历没毛病。关键就是括号问题，仔细观察发现，括号是把左右子树分别括了起来，只有一个左右节点的不加括号； 比如：
这种情况输出结果是BAC,而不是（B）A（C） 二叉树的解题关键要把规模缩小，只着眼于三个节点的基本二叉树模型，通过递归解决问题，否则无从下手。所以有三种情况，分别是左右均有孩子；只有右孩子（因为是中缀树，不存在只有左孩子情况）；左右均没有孩子。然后分类解决即可。
更新：仔细观察发现，代码一的思路之所以复杂是因为强制加了括号，这自然导致加上了多余的括号，所以要进行后续的筛选。 那么可以尝试分类：思考什么情况下需要加括号？观察不难发现，只有根节点和叶子节点不加括号，换句话讲所加的括号包括了整个非空子树。 请见示例代码二
示例代码一(不推荐)
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std
;
struct node
{
public:
string str
;
int left
= -1, right
= -1;
};
vector
<node
> vec
;
vector
<string
> s1
;
void func(int root
) {
if (vec
[root
].left
!= -1 && vec
[root
].right
!= -1) {
s1
.push_back("(");
func(vec
[root
].left
);
s1
.push_back(")");
s1
.push_back(vec
[root
].str
);
s1
.push_back("(");
func(vec
[root
].right
);
s1
.push_back(")");
}
if (vec
[root
].left
== -1 && vec
[root
].right
!= -1) {
s1
.push_back(vec
[root
].str
);
s1
.push_back("(");
func(vec
[root
].right
);
s1
.push_back(")");
}
if (vec
[root
].left
== -1 && vec
[root
].right
== -1) {
s1
.push_back(vec
[root
].str
);
}
}
int main() {
int n
, left
, right
;
scanf("%d", &n
);
vec
.resize(n
+ 1);
vector
<bool> isroot(n
+ 1);
for (int i
= 1; i
<= n
; i
++) {
cin
>> vec
[i
].str
;
scanf("%d %d", &left
, &right
);
if (left
!= -1) {
vec
[i
].left
= left
;
isroot
[left
] = true;
}
if (right
!= -1) {
vec
[i
].right
= right
;
isroot
[right
] = true;
}
}
int Root
;
for (Root
= 1; Root
<= n
&& isroot
[Root
]; Root
++);
func(Root
);
int pre
= 0;
vector
<bool> isout(s1
.size(),true);
for (int i
= 0; i
< s1
.size(); i
++) {
if (s1
[i
] == "(") {
pre
= i
;
}
else if (s1
[i
] == ")") {
if (i
- pre
== 2) {
isout
[pre
] = false;
isout
[i
] = false;
}
}
}
for (int i
= 0; i
< s1
.size(); i
++) {
if (isout
[i
]) cout
<< s1
[i
];
}
return 0;
}
示例代码二(推荐)
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
using namespace std
;
struct node
{
public:
string str
;
int left
= -1, right
= -1;
};
vector
<node
> vec
;
int Root
;
void preorder(int index
, int deep
) {
if (index
== -1) return;
if (vec
[index
].left
== -1 && vec
[index
].right
== -1) {
printf("%s", vec
[index
].str
.c_str());
}
else {
if (deep
> 0) printf("(");
preorder(vec
[index
].left
, deep
+ 1);
printf("%s", vec
[index
].str
.c_str());
preorder(vec
[index
].right
, deep
+ 1);
if(deep
> 0) printf(")");
}
}
int main() {
int n
, left
, right
;
scanf("%d", &n
);
vec
.resize(n
+ 1);
vector
<bool> isroot(n
+ 1);
for (int i
= 1; i
<= n
; i
++) {
cin
>> vec
[i
].str
;
scanf("%d %d", &left
, &right
);
if (left
!= -1) {
vec
[i
].left
= left
;
isroot
[left
] = true;
}
if (right
!= -1) {
vec
[i
].right
= right
;
isroot
[right
] = true;
}
}
for (Root
= 1; Root
<= n
&& isroot
[Root
]; Root
++);
preorder(Root
, 0);
return 0;
}
