欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1130 Infix Expression

程序员文章站 2022-07-01 15:16:03
...
1130 Infix Expression1130 Infix Expression

题目大意

给出一棵树,让你输出中缀表达式。但是要符合括号格式。

思路解析

既然是中缀表达式妥妥的中序遍历没毛病。关键就是括号问题,仔细观察发现,括号是把左右子树分别括了起来,只有一个左右节点的不加括号;
比如:

1130 Infix Expression
这种情况输出结果是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;
}