二叉搜索树+前序遍历 -> 后序遍历

末蓝、 2022-07-12 03:14 343阅读 0赞

[sdut原题链接][sdut]

迷失の搜索树  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
小璐在机缘巧合之下获得了一个二叉搜索树，这个二叉搜索树恰好有n个节点，每个节点有一个权值，每个节点的权值都在\[1,n\]这个区间内，并且两两不相同，真是优美的性质啊  
但是命运的不公又让她失去了这个二叉搜索树  
幸运的是，她还记得自己丢失的二叉搜索树的前序遍历序列。  
在丢了二叉搜索树之后，小璐无比想念她的这个树的后序遍历  
那么问题来了，聪明的你在知道这个二叉搜索树的前序遍历的序列的情况下，能帮她找到这个二叉搜索树的后序遍历嘛?

Input  
多组输入，以文件结尾  
每组数据第一行为一个整数n，代表这个二叉搜索树的节点个数(1<=n<=100)  
接下来一行n个整数，代表这个二叉搜索树的前序遍历序列

Output  
输出n个整数  
表示这个二叉树的后序遍历序列

Example Input  
5  
4 2 1 3 5

Example Output  
1 3 2 5 4

Hint  
二叉查找树是一棵空树，或者是具有下列性质的二叉树：  
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值  
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值  
它的左、右子树也分别为二叉排序树  
Author  
2016暑假集训结训赛 by QAQ

以下为accepted代码

#include <stdio.h>
    #include <stdlib.h>
    typedef struct node
    {
        int date;
        struct node *left;
        struct node *right;
    }BinTree;
    BinTree *root;
    int num[140], flag;
    BinTree * Insert(BinTree *rt, int x)//二分查找树的插入算法
    {
        if(!rt){
            rt = (BinTree *)malloc(sizeof(BinTree));
            rt->date = x;
            rt->left = rt->right = 0;
        }
        else
        {
            if(x < rt->date)
                rt->left = Insert(rt->left, x);
            else
                rt->right = Insert(rt->right, x);
        }
        return rt;
    }
    void last_put(BinTree *rt)//中序遍历
    {
        if(rt)
        {
            last_put(rt->left);
            last_put(rt->right);
            num[flag++] = rt->date;
        }
    }
    int main()
    {
        int n, i, x;
        while(scanf("%d", &n) != EOF)
        {
            flag = 0;///注意初始化
            root = NULL;///注意初始化
            for(i = 0; i < n; i++)
            {
                scanf("%d", &x);
                root = Insert(root, x);//调用二分查找树的插入函数
            }
            last_put(root);//调用中序遍历函数
            for(i = 0; i < n; i++)
            {
                printf("%d%c", num[i], i == n-1? '\n': ' ');
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 8ms
    Take Memory: 584KB
    Submit time: 2017-02-08 18:26:18
    ****************************************************/

以下为runtime error代码

#include <stdio.h>
    #include <stdlib.h>
    typedef struct node
    {
        char date;
        struct node *left;
        struct node *right;
    } BinTree;
    BinTree *rt;
    int num[140];
    int flag;
    BinTree * get_build(int len, char *st1, char *st2)
    {
        if(len == 0)
            return NULL;
        int i;
        BinTree *root;
        root = (BinTree *)malloc(sizeof(BinTree));
        root->date = st1[0];
        for(i = 0; i < len; i++)
        {
            if(st2[i] == root->date)
                break;
        }
        root->left = get_build(i, st1+1, st2);
        root->right = get_build(len-i-1, st1+i+1, st2+i+1);
        num[flag++] = root->date - '0';
        return root;
    }
    int cmp(const void *a, const void *b)
    {
        return ((*(char *)a)-(*(char *)b));
    }
    int main()
    {
        int n, i, x;
        char st1[140], st2[140];
        while(scanf("%d", &n) != EOF)
        {
            for(i = 0; i < n; i++)
            {
                scanf("%d", &x);
                st1[i] = x + '0';
                st2[i] = st1[i];
            }
            qsort(&st2[0], n, sizeof(st2[0]), cmp);
            ///printf("%s\n", st2);
            rt = get_build(n, st1, st2);
            for(i = 0; i < n; i++)
            {
                printf("%d%c", num[i], i == n-1? '\n': ' ');
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Runtime Error
    Take time: 0ms
    Take Memory: 0KB
    Submit time: 2017-02-08 17:54:56
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2006/pid/3653