首页 > 代码库 > 给先序中序构造后序

给先序中序构造后序

代码:

#include <iostream>
using namespace std;
void build(int n,char* s1,char *s2,char *s)
{
    if (n <= 0)return;
    int p = strchr(s2, s1[0]) - s2;//找到根结点在中序遍历中的位置
    build(p, s1 + 1, s2, s);//递归构造左子树的后序遍历
    build(n - p - 1, s1 + p + 1, s2 + p + 1, s + p);//递归构造右子数的后序遍历
    s[n - 1] = s1[0];
}
int main()
{
    char s1[1000], s2[1000];
    while (scanf("%s%s", s1, s2) == 2)
    {
        int n = strlen(s1);
        char s[1000];
        build(n, s1, s2, s);
        s[n] = \0;
        printf("%s\n", s);
    }
}

语法说明:

strchr()

头文件:#include <string.h>
strchr() 用来查找某字符在字符串中首次出现的位置,其原型为:char * strchr (const char *str, int c);

 

思路:

此题思路还算比较明晰,但是代码写起来很难写到这么简洁。

给先序中序构造后序