已知中序、后序，求先序

已知中序、后序，求先序

 题目：[NOIP2001]求先序排列

 参考题解：[NOIP2001]求先序排列题目题解

首先举例：

中序： FDBEG A CH
后序： FDGEB HC A

设递归函数名为void xian（string s1,string s2）

0. 定义 len1是中序的长度，len2是后序的长度，如果后序的长度小于等于0，return；

（例子中 len1=len2=8 ）

1. 后序的最后一个字母是先序的第一个字母，定义字符 ch=这个字母，输出这个字符；

（例子中输出A）

2. 在 中序 中 找到 字符ch 的下标，记为pos；

（例子中pos=5）

【用string的 find 函数，关于 find函数 可见这篇博客：C++ string中的find()函数 - 博客园】

3. 以pos为分界线，开始递归 中序pos 的【0，pos) 和 【pos+1，len1）；

（例子中的 左边FDBEG 和 右边CH）

    对应的是 后序序列的【0，pos)部分和【pos，len2-1）；

（例子中的 左边FDGEB 和 右边HC）

    这时可以用string的substr函数：substr（C++语言函数）_百度百科

    substr的参数是起点和长度，所以递归写成：xian(s1.substr(0,pos) , s2.substr(0,pos));//左

                                      和 xian (s1.substr(pos+1,len1-pos-1),s2.substr(pos,len2-1-pos));//右

---

如果写法上简略一点的话，可以写成：

 xian(s1, s2.substr(0,pos));和xian (s1.substr(pos+1),s2.substr(pos,len2-1-pos));

---

代码：

#include
using namespace std;
char s1[10],s2[10];
void xian(string s1,string s2){
    int len1=s1.size();
    int len2=s2.size();
    if(len2<=0)return;
    char c=s2[len2-1];cout<>s1>>s2;
    xian(s1,s2);
	return 0;
 }