洛谷P1305题解

洛谷P1305题解

题目传送门：https://www.luogu.com.cn/problem/P1305#submit

题目简述：

输入一个二叉树，需要输出先序遍历，二叉树的输入格式是字符串，每一行有三个元素abc表示b,c是a的左右孩子

数据规模：n<=26

题目分析：

思路很显然，先储存二叉树，然后再先序遍历输出。

1. 储存二叉树可以用left[maxn],right[maxn]分别储存左右孩子，由于是字符型可以ch-'a'变成数组的下标进行储存
2. 先序遍历的方式就是一个递归函数函数先输出root然后对左子树递归，对右子树递归

代码：

#include<cstdio>
#include<cstring>

using namespace std;

const int maxn = 1000;
int left[maxn], right[maxn];

void root_first(int root) {
	printf("%c", 'a' + root);
	if (left[root] != -1)root_first(left[root]);
	if (right[root] != -1)root_first(right[root]);
}

int main() {
	int n;
	scanf("%d", &n);
	memset(left, -1, sizeof(left));
	memset(right, -1, sizeof(right));
	char str[4];
	int r;
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		if (i == 0)r = str[0] - 'a';
		if(str[1] != '*')left[str[0] - 'a'] = str[1] - 'a';
		if(str[2] != '*')right[str[0] - 'a'] = str[2] - 'a';
	}
	root_first(r);
	printf("\n");
	return 0;
}

最后