L2-011 玩转二叉树（25 分）

旧城等待， 2022-05-24 02:47 176阅读 0赞

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

**输入格式：**

输入第一行给出一个正整数N（<=30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

**输出格式：**

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

**输入样例：**

7
    1 2 3 4 5 6 7
    4 1 3 2 6 5 7

**输出样例：**

4 6 1 7 5 3 2

代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<queue>
    using namespace std;
    int a[50],b[50];
    struct node
    {
        int data;
        struct node *lchild,*rchild;
    };
    struct node * create(int n,int a[],int b[])
    {
        if(n<=0)
        {
            return NULL;
        }
        struct node *root=(struct node *)malloc(sizeof(struct node));
        root->data=b[0];
        root->lchild=root->rchild=NULL;
        int *p;
        for(p=a;p<a+n;p++)
        {
            if(*p==b[0])
                break;
        }
        int t=p-a;
        root->lchild=create(t,a,b+1);
        root->rchild=create(n-t-1,p+1,b+t+1);
        return root;
    };
    int flag=0;
    void cengci(struct node *root)
    {
        queue<struct node *> que;
        que.push(root);
        while(!que.empty())
        {
            struct node *tmp=que.front();
            que.pop();
            if(tmp)
            {
                if(flag==0)
                {
                    printf("%d",tmp->data);
                    flag=1;
                }
                else
                {
                    printf(" %d",tmp->data);
                }
                que.push(tmp->rchild);
                que.push(tmp->lchild);
            }
        }
    }
    int main()
    {
        int i,j,n,m,k,t;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
        }
        struct node *root=create(n,a,b);
        cengci(root);
        return 0;
    }