求先序遍历

wlqtc · 2020-03-27 09:23:04 · 个人记录

第一次写555

题目：输入中序遍历和后序排列(字母)，输出先序遍历。

上学期刚学数据结构，然后现在就快忘记啥是中序和后序遍历了。

数据结构考试也有类似的题，当时解这种题的方法就是，先找后序遍历里面最靠后的点，在中序遍历中圈出来，这样圈起来的就是根结点，左边就是左子树，右边就是右子树（因为中序遍历实际上就是树的投影），然后对左子树，右子树也是相同的处理。（就可以想到用递归解题了）

所以就可以找出中序遍历的每个点，在后序遍历是什么位置，用数组存起来。这一题的数据范围比较小，随便循环。

可能这个方法又笨又耗时吧555

记录一下，防止自己以后再忘记啥是中后序遍历了

#include<bits/stdc++.h>
using namespace std;
char s[10];
char c[10];
int a[10];
void f(int x,int y)
{
    if(x>y)return ;
    int pos;
    int maxx=-1;
    for(int i=x; i<=y; i++)//找最大值，就是最靠后的，就是找子树的根结点
    {
        if(a[i]>maxx)
        {
            maxx=a[i];
            pos=i;
        }
    }
    printf("%c",s[pos]);
    f(x,pos-1);//左子树
    f(pos+1,y);//右子树
}
int main()
{

    scanf("%s%s",s,c);
    int len=strlen(s);
    for(int i=0; i<len; i++)
    {
        for(int j=0; j<len; j++)
        {
            if(s[i]==c[j])//记录中序遍历的每个点在先序遍历中的位置
            {
                a[i]=j;
                break;
            }
        }
    }
    f(0,len-1);
    printf("\n");
    return 0;
}