Description
给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
Input
输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。
Output
在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
Sample Input
7
12 3 4 5 6 7
41 3 2 6 5 7
Sample Output
46 1 7 5 3 2
参考程序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LEN 40
#define ROOM sizeof(struct TreeNode)
struct TreeNode
{
int number;
struct TreeNode *lchild;
struct TreeNode *rchild;
};
int InOrder[LEN+5],PreOrder[LEN+5];
struct TreeNode* CreateTree(int InStart,int InEnd,int PreStart,int PreEnd)
{
struct TreeNode *r;
int i,cnt=0;
r=(struct TreeNode*)malloc(ROOM);//分配空间是必须的！
r->number=PreOrder[PreStart];
for(i=InStart;i<=InEnd;i++)
{
//在中序遍历序列中寻找根结点
if(InOrder[i]==r->number)
{
break;
}
cnt++;
}
if(i-InStart==0)
{
r->lchild=NULL;
}
else
{
r->lchild=CreateTree(InStart,i-1,PreStart+1,PreStart+cnt);
}
if(InEnd-i==0)
{
r->rchild=NULL;
}
else
{
r->rchild=CreateTree(i+1,InEnd,PreStart+1+cnt,PreEnd);
}
return r;
}
void Adjust(struct TreeNode *T)
{
if(T)
{
struct TreeNode *temp;
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
Adjust(T->lchild);//递归调整左子树
Adjust(T->rchild);//递归调整右子树
}
}
void LevelVisit(struct TreeNode *T,int N)
{
int first=0,cnt=1,i;
struct TreeNode* queue[LEN+5];
queue[0]=T;
while(cnt<N)
{
if(queue[first]->lchild)
{
queue[cnt++]=queue[first]->lchild;
}
if(queue[first]->rchild)
{
queue[cnt++]=queue[first]->rchild;
}
first++;
}
for(i=0;i<cnt-1;i++)
{
printf("%d ",queue[i]->number);
}
printf("%d\n",queue[i]->number);
}
int main()
{
int N,i;
struct TreeNode *Tree;
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d",&InOrder[i]);
}
for(i=0;i<N;i++)
{
scanf("%d",&PreOrder[i]);
}
Tree=CreateTree(0,N-1,0,N-1);
Adjust(Tree);
LevelVisit(Tree,N);
return 0;
}
把握住中序遍历的主要思想是“左-根-右”，前序遍历的思想是“根-左-右”，这样前序遍历序列的第一个结点一定是树/子树的根结点，那么回到中序遍历中，该结点的左边部分序列全部属于左子树、右边部分序列全部属于右子树；这样一来一个串就被拆分出两个子串，递归处理两个子树的中序遍历序列、前序遍历序列即可。
镜面对称操作类似于树的遍历，通过遍历把所有结点的左右子树均交换即可。
最后层序遍历经镜面对称调整的二叉树即可。
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: