♐ CSP_J 组真题
2001年
3. 求先序排列

线上OJ:

线上OJ:
一本通:1916:【01NOIP普及组】求先序排列 (opens in a new tab)
AcWing:5498. 求先序排列 (opens in a new tab)
洛谷:P1030 [NOIP2001 普及组] 求先序排列 (opens in a new tab)

核心思想:

1、先构建二叉树,再按照要求输出
2、构建的方法,可以使用字符数组,也可以使用字符串
3、构建树的核心是:通过递归,根据后序遍历和中序遍历构建树

💡

第一步、后序遍历的最后一个一定是根
第二步、在中序遍历中找到根
第三步、根左侧的都为左子树,右侧的都为右子树。对左子树和右子树分别再次递归

传入参数说明:
int left_pos, int right_pos:待构建树的后序遍历的左右坐标
int left_mid, int right_mid:待构建树的中序遍历的左右坐标

使用字符数组 构建树
#include <bits/stdc++.h>
using namespace std;
 
const int N = 105;
char s1[N], s2[N];  // s1 中序遍历,s2 后序遍历 
 
struct Node
{
	char val;			// 存储当前节点的编号 
	int lchild, rchild;	// 存储当前节点的左子树和右子树节点的编号 
};
Node node[N];
int p = 0; 	// 存储节点编号 
 
/*
核心思想:通过递归,根据后序遍历和中序遍历创建树
 第一步、后序遍历的最后一个一定是根
 第二步、在中序遍历中找到根
 第三步、根左侧的都为左子树,右侧的都为右子树。对左子树和右子树分别再次递归 
 传入参数说明:
 int left_pos, int right_pos:待构建树的后序遍历的左右坐标
 int left_mid, int right_mid:待构建树的中序遍历的左右坐标
*/ 
int creatTree(int left_pos, int right_pos, int left_mid, int right_mid)
{
	if(left_pos > right_pos || left_mid > right_mid) 	// 判断递归退出边界 
		return 0;
	
	int id = ++p;	// 如果没越界,则为该节点创建新的编号
	node[id].val = s2[right_pos]; 	// 第一步、后序遍历的最后一个一定是根 
	
	// 第二步、在中序遍历中找到根。根左侧的都为左子树,右侧的都为右子树
	int len;	// 当找到根节点后,用于存储左子树的长度 
	int i; 		// 用于存储找到的根的下标 
	for(i = left_mid; i <= right_mid; i++)
	{
		if( s1[i] == s2[right_pos] ) // 在中序遍历中找根(根为后续遍历的最后一个) 
		{
			len = i - left_mid;  // i坐标前面的,是左子树的长度 
			break;
		}			
	} 	
	
	// 第三步、根左侧的都为左子树,右侧的都为右子树。对左子树和右子树分别再次递归。
	node[id].lchild = creatTree(left_pos, left_pos + len - 1, left_mid, i - 1);
	node[id].rchild = creatTree(left_pos + len, right_pos - 1, i + 1, right_mid);
	
	return id;
} 
 
void preOrder(int id)
{
	if(id == 0)   return;
	cout << node[id].val;
	preOrder(node[id].lchild);
	preOrder(node[id].rchild);
}
 
int main()
{
	cin >> s1 >> s2;
	int len_s1 = strlen(s1);
	int len_s2 = strlen(s2);
	int root = creatTree(0, len_s2 - 1, 0, len_s1 - 1);	// 创建树 
	preOrder(root);	// 后续遍历输出节点 	
}