2001NOIP普及组真题 3. 求先序排列

本文主要是介绍2001NOIP普及组真题 3. 求先序排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线上OJ：

线上OJ：
【01NOIP普及组】求先序排列

核心思想：

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);	// 后续遍历输出节点 	
}

解法二、使用字符串构建树

#include <bits/stdc++.h>
using namespace std;const int N = 105;
string s1, s2;  // s1 中序遍历，s2 后序遍历 struct Node
{char val;			// 存储当前节点的编号 int lchild, rchild;	// 存储当前节点的左子树和右子树节点的编号 
};
Node node[N];
int p = 0;	// 存储节点编号int createTree(string sp, string si)//用后序序列sp与中序序列si构建二叉树，返回树根 
{int id = ++p;node[id].val = sp[sp.length()-1];int i = si.find(node[id].val);		// 在中序遍历中找到根，利用 string的 s.find() 函数即可，返回即为索引 int len_l = i, len_r = si.length() - 1 - i;//左右子树序列长度 //序列长度大于0，才可以建立一棵树if(len_l > 0)  node[id].lchild = createTree(sp.substr(0, len_l), si.substr(0, len_l));if(len_r > 0)  node[id].rchild = createTree(sp.substr(len_l, len_r), si.substr(len_l + 1, len_r));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 root = createTree(s2, s1);preOrder(root);return 0;
}

解法三、不构建树，直接输出

#include <bits/stdc++.h>
using namespace std;string s1, s2;  // s1 中序遍历，s2 后序遍历 void calc(int left_pos, int right_pos, int left_mid, int right_mid)
{cout << s2[right_pos];  // 这一行的位置决定了输出结果是先序遍历还是后序遍历int i = s1.find(s2[right_pos]);		// 第一步、后序遍历的最后一个一定是根。根据这个“根”，在中序遍历中找到其坐标 i int len = i - left_mid;// 在中序遍历中，如果 i 不是左边界（即 i > left_mid），则说明有左子树。需要进行递归if(i > left_mid) calc(left_pos, left_pos + len - 1, left_mid, i - 1);	// 在中序遍历中，如果 i 不是右边界（即 i < right_mid），则说明有右子树。需要进行递归 if(i < right_mid) calc(left_pos + len, right_pos - 1, i + 1, right_mid);// cout << s2[right_pos];  // 这一行的位置决定了输出结果是先序遍历还是后序遍历。放在此处就是后序遍历
}int main()
{cin >> s1 >> s2;calc(0, s2.length() - 1, 0, s1.length() - 1);cout << endl;return 0;
}