迷失の搜索树

叁歲伎倆 2022-07-12 03:56 119阅读 0赞

#### 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 ####

二叉查找树是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

它的左、右子树也分别为二叉排序树

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    typedef struct node
    {
        int data;
        struct node *lc,*rc;
    }bitree;
    int flag;
    bitree * create(bitree * t,int x)
    {
        if(!t)
        {
            t=(bitree *)malloc(sizeof(bitree));
            t->data=x;
            t->lc=t->rc=NULL;
            return t;
        }
        if(x<t->data)
        {
            t->lc=create(t->lc,x);
        }
        else
        {
            t->rc=create(t->rc,x);
        }
        return t;
    }
    int a[100];
    int j=-1;
    void postshow(bitree * t)
    {
        if(t)
        {
            postshow(t->lc);
            postshow(t->rc);
            a[++j]=t->data;
        }
    }
    int main()
    {
        int i,n,x;
        bitree * tree;
        while(scanf("%d",&n)!=EOF)
        {
            j=-1;
            tree=(bitree *)malloc(sizeof(bitree));
            scanf("%d",&tree->data);
            tree->lc=tree->rc=NULL;
            n--;
            while(n--)
            {
                scanf("%d",&x);
                tree=create(tree,x);
            }
            postshow(tree);
            for(i=0;i<=j;i++)
            {
                printf("%d%c",a[i],i==j?'\n':' ');
            }
        }
        return 0;
    }