算法训练 求先序排列（递归 ，蓝桥杯C++，简洁算法、代码）

优化算法训炼 求先序排序

資源限定
时间限制：1.0s 运行内存限定：256.0MB
难题叙述
　　得出一棵二叉树的中序与之后排序。算出它的先序排序。（承诺树节点用不一样的英文大写字母表明，长短<=8）。
键入文件格式
　　二行，每排一个字符串数组，各自表明中序和之后排序
輸出文件格式
　　一个字符串数组，表明所愿先序排序

示例键入
　　BADC
　　BDCA
示例輸出
ABCD

序言：尽管它是一道很基本的一道题，可是我看到一种出色构思，我也要想纪录到blog里。

构思与分析：

这是一个给中序和之后求先序的题，大家大约的观念便是在先序中找到和之后最终一个字符（头节点）一样的标识符的部位，复印出去，随后他的左边便是左小孩，右边便是右小孩，随后再将左小孩的串递归进来，找根上下，沒有左小孩了return回家找右小孩，在将右小孩串找左小孩，递归递归递归 递归……

1、例如大家拿事例中的
中序：BADC
之后：BDCA

最先在中国序寻找之后的最终一个字符 “A” , 寻找他的字符是 1 ，并打印A，由于他是根，随后这时候之后就剩DBC,中序分成了左子串“B”和右子串“DC”。

for(int i = 0;i < r1 ;i++)		//解析xml中序中连接点
    {
        if(a[i] == b[r2 - 1])	//寻找和结尾一样的标识符
        {
            printf("%c",a[i]);	//复印根
            k = i;				//纪录字符
        }
    }

2、大家再依次把他的左子树和右子树递归进来

 if( k > l1) tree(l1, k, l2, l2 + k - l1);
 if(k + 1 < r1) tree(k+1, r1,l2 + k - l1,r2 -1);

k是根节点再中序串中的座标，那麼假如根节点的座标没有中序串的第一个部位，即 k > l1 ，则意味着他也有左小孩，那麼就打开网址他的左小孩，那麼左小孩的临界值座标应该是 l1和 k （这儿为什么是k而不是k - 1,是由于在每一次解析xml是以i = 0;i < r1 ;i++，因此 i 是< k的），右小孩的临界值座标是 l2 和 l2 + k - l1,我们知道之后串中根节点的左小孩一定是以字符为0逐渐的，由于是上下根嘛，那麼左临界值是l2没有问题，那麼右临界值就是以l4开始往右边数左小孩的数量，例如左小孩只有一个B，那便是挪动一位，即 l2 + k - l1，（k - l1 就意味着在根节点以前左小孩长短多少钱），那麼直至沒有左小孩了以后递归出去，逐渐递归右小孩，同样k+1, r1,l2 + k - l1,r2 -1这四个主要参数我觉得也无需多讲，k的下一位到最右边，和左小孩右边逐渐到最终早已复印过的连接点字符以前。

那麼到这儿早已很详尽的表明了递归全过程，下边就上详细编码：

#include
#include
using namespace std;
 char a[10];
 char b[10];

int tree(int l1,int r1,int l2,int r2)//中序之后逐渐都是0到r1
{
	int k;
	for(int i = 0;i < r1 ;i++)
    {
        if(a[i] == b[r2 - 1])		//寻找根
        {
            printf("%c",a[i]);		//复印根
            k = i;			//纪录字符
        }
    }
    if( k > l1) tree(l1, k, l2, l2 + k - l1);	//如果有左小孩就一直递归
    if(k + 1 < r1) tree(k+1, r1,l2 + k - l1,r2 -1);		//左小孩递归完后后逐渐递归右小孩
}
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    int lenth1 = strlen(a);			//length 是中序
    int lenth2 = strlen(b);			//length 是之后
    tree(0,lenth2,0,lenth2);
	return 0;
}

在大家学好得出 中 后 算先序，大家再试一下得出中 先 算之后（自然不太可能是给依次算中序，由于要是没有中序你没法明确上下小孩的部位）

我依据一样的观念也想到了类似的方式 ：
大家的观念還是一样，最先寻找根节点（中序遍历和先序的第一个做 == ）

for(int i = 0;i < r1 ;i++)
    {
        if(a[i] == b[l2])
        {
            k = i;
        }
    }

可是找到并不复印，只是递归他的上下子串，直至最下边的连接点早已沒有小孩（上下也没有）了，复印该连接点

	if( k > l1) tree(l1 , k, l2 + 1 , l2 + 1  + k - l1);//cout<<"1";
    if(k + 1 < r1) tree(k+1, r1,l2 + 1 + k - l1,r2);
    printf("%c",a[k]);

这儿的上下临界值大伙儿自身去思索一下为何吧，时尚博主就不会再表述了，和上边的如出一辙；

详细编码：

#include
#include
using namespace std;
 char a[10];
 char b[10];

int tree(int l1,int r1,int l2,int r2)
{
	int k;
	for(int i = 0;i < r1 ;i++)
    {
        if(a[i] == b[l2])
        {
            k = i;
        }
    }
    if( k > l1) tree(l1 , k, l2 + 1 , l2 + 1  + k - l1);//cout<<"1";
    if(k + 1 < r1) tree(k+1, r1,l2 + 1 + k - l1,r2);
     printf("%c",a[k]);
}
int main()
{
    scanf("%s",a);
    scanf("%s",b);
    int lenth1 = strlen(a);
    int lenth2 = strlen(b);
    tree(0,lenth2,0,lenth2);
	return 0;
}

后语：这道题看过巨头的文章内容构思顿开，自身也再次计算出了给先中序求之后的编码，今日收获满满，假如文章内容另当别论，还期待大伙儿多多的不吝赐教！