给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
输入
输入第一行给出一个正整数N（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<iostream> #define MaxSize 30 using namespace std; struct BTNode { int data; BTNode* lchild; BTNode* rchild; }; class BTNodeClass { BTNode* r; public: BTNodeClass(); ~BTNodeClass(); void LevelOrder(); BTNode* BTreeFromOrderings(int* inorder, int* preorder, int length); }; BTNodeClass::BTNodeClass() { r = NULL; } BTNodeClass::~BTNodeClass() { } BTNode* BTNodeClass::BTreeFromOrderings(int* inorder, int* preorder, int length) { BTNode* p=new BTNode(); if (length == 0) { return NULL; } if (r == NULL)r = p; p->data = *preorder; int rootIndex; for (rootIndex = 0; rootIndex<length; rootIndex++) { if (inorder[rootIndex] == *preorder) break; } p->lchild = BTreeFromOrderings(inorder, preorder + 1, rootIndex); p->rchild = BTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - rootIndex - 1); return p; } void BTNodeClass::LevelOrder() { static bool flag = true; BTNode* p; BTNode* q[MaxSize]; int front = 0, rear = 0; rear++; q[rear] = r; while (front != rear) { front = (front + 1) % MaxSize; p = q[front]; if (flag) { cout << p->data; flag = false; } else cout << " " << p->data; if (p->rchild != NULL) { rear = (rear + 1) % MaxSize; q[rear] = p->rchild; } if (p->lchild != NULL) { rear = (rear + 1) % MaxSize; q[rear] = p->lchild; } } } int main() { int n,i; int a[MaxSize], b[MaxSize]; cin >> n; for (i = 0; i < n; i++) { cin >> a[i]; } for (i = 0; i < n; i++) { cin >> b[i]; } BTNodeClass tree; tree.BTreeFromOrderings(a, b, i); tree.LevelOrder(); return 0; }