[数据结构与算法]树的还原及层序遍历—7-26玩转二叉树

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

输入格式：
输入第一行给出一个正整数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 <bits/stdc++.h>
using namespace std;
typedef int elemType;//节点类型定义。
typedef struct BiNode
{
    elemType data;
    struct BiNode *Lchild,*Rchild;
}BiNode,*BiTree;
BiTree creatTree(int *ArrayF,int *ArrayM,int Len)//树的还原(递归法)
{
    BiTree T;
    int i;
    if(Len==0) return NULL;
    T=(BiTree)malloc(sizeof(BiNode));
    T->data=ArrayF[0];
    for(i=0;i<Len;i++)
        if(ArrayF[0]==ArrayM[i]) break;
    T->Lchild=creatTree(ArrayF+1,ArrayM,i);
    T->Rchild=creatTree(ArrayF+i+1,ArrayM+i+1,Len-i-1);
    return T;
}
void flipTree(BiTree T)//树的镜面反转，即交换非叶子节点的左右孩子。
{
    if(T!=NULL)
    {
         BiTree t;
         t=(BiTree)malloc(sizeof(BiNode));//t为交换时的中间变量。
         t=T->Lchild;
         T->Lchild=T->Rchild;
         T->Rchild=t;
         flipTree(T->Lchild);//递归对左右孩子进行相同操作
         flipTree(T->Rchild);
    }
}
void LevelVist(BiTree T)//树的层序遍历
{
    int i=0;
    queue<BiNode*> q;
    q.push(T);
    while(!q.empty())//使用队列进行，根节点压入后，遍历一个节点同时压入其左右孩子，并且出队这个节点。
    {
        if(!i) {cout<<(q.front())->data;i++;}//i用来控制输出节点之间恰好有一个空格.
        else cout<<" "<<(q.front())->data;
        if((q.front())->Lchild!=NULL) q.push((q.front())->Lchild);
        if((q.front())->Rchild!=NULL) q.push((q.front())->Rchild);
        q.pop();
    }
}
int main()
{
    int n;
    cin>>n;
    int First[n],Mid[n];
    for(int i=0;i<n;i++)
        cin>>Mid[i];
    for(int i=0;i<n;i++)
        cin>>First[i];
    BiTree T=(BiTree)malloc(sizeof(BiNode));
    T=creatTree(First,Mid,n);
    flipTree(T);
    LevelVist(T);
    return 0;
}