题目描述
假设二叉树用二叉链表存储，用先序序列结果创建。输入二叉树的先序序列，请你先创建二叉树，并对树做个镜面反转，再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。
--程序要求--
程序中不允许使用STL库等第三方对象或函数实现本题的要求
输入
测试次数t
每组测试数据是一个二叉树的先序遍历序列，#表示空树
输出
对每棵二叉树，输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树，输出四个NULL（后面不加空格，每个NULL独自一行，中间没有空行）。如下：
NULL
NULL
NULL
NULL
输入样例1
3 41#32###65##7## AB#C##D## AB##C##
输出样例1
4 6 7 5 1 3 2 7 6 5 4 3 2 1 7 5 6 2 3 1 4 4 6 1 7 5 3 2 A D B C D A C B D C B A A D B C A C B C A B C B A A C B
思路分析
我们假设你已经会了先序遍历、中序遍历、后序遍历和层次遍历。
那么这道题其实非常简单，我们只需要在建树的时候，把原来的建树顺序改变一下即可，即，先建立右子树，再建立左子树。
然后因为这道题说不能用STL，但是你的BFS，也就是你的层次遍历需要一个队列，所以你需要自己实现一个队列，在小数据的范围内，写一个简单的队列还是很简单的，用一个定长的数组，加上滑动双下标就可以实现一个队列了，当然是有范围的队列。
AC代码
代码语言：javascript复制#include <iostream>
#include <string>
using namespace std;
class BiTreeNode {
public:
char data; //数据域
int weight = 0;
BiTreeNode *leftChild, *rightChild; //左右子树指针
BiTreeNode() : leftChild(NULL), rightChild(NULL) {}
~BiTreeNode() {}
};
class mySTL {
public:
BiTreeNode *volume[10000];
int front = 0;
int rear = 0;
BiTreeNode *top() {
return volume[front];
}
void pop() {
front ;
}
void push(BiTreeNode *item) {
volume[rear ] = item;
}
bool empty() {
if (front == rear)
return true;
return false;
}
};
class BiTree {
private:
BiTreeNode *root; //根结点指针
string sTree; //建树字符串
int pos; //标识建树字符串的当前字符位置
BiTreeNode *CreateTree();//建树私有函数
public:
int maxPath = 0;
BiTree() : root(NULL) {};
void Create(string vArray); //建树公有接口，参数是特定的先序遍历字符串
void LevelOrder(BiTreeNode *T) {
mySTL open;
BiTreeNode *p = T;
if (p)
open.push(p);
while (!open.empty()) {
p = open.top();
open.pop();
if (p) {
cout << p->data<<' ';
open.push(p->leftChild);
open.push(p->rightChild);
}
}
cout << endl;
}
void PreOrder(BiTreeNode *T) {
if (T == NULL)
return;
cout << T->data<<' ';
PreOrder(T->leftChild);
PreOrder(T->rightChild);
}
void InOrder(BiTreeNode *T) {
if (T == NULL)
return;
InOrder(T->leftChild);
cout << T->data<<' ';
InOrder(T->rightChild);
}
void PostOrder(BiTreeNode *T) {
if (T == NULL)
return;
PostOrder(T->leftChild);
PostOrder(T->rightChild);
cout << T->data<<' ';
}
void Show() {
if(root==NULL){
cout<<"NULL"<<endl<<"NULL"<<endl<<"NULL"<<endl<<"NULL"<<endl;
}
PreOrder(root);
cout << endl;
InOrder(root);
cout << endl;
PostOrder(root);
cout << endl;
LevelOrder(root);
}
};
void BiTree::Create(string vArray) {
pos = 0;
sTree.assign(vArray); //把参数保存到内部字符串
root = CreateTree(); //建树成功后root指向根结点
}
BiTreeNode *BiTree::CreateTree() {
if (pos == sTree.size() || sTree[pos] == '#') {
pos ;
return NULL;
}
BiTreeNode *T = new BiTreeNode();
T->data = sTree[pos ];
T->rightChild = CreateTree();
T->leftChild = CreateTree();
return T;
}
int main() {
int t;
string temp;
cin >> t;
while (t--) {
cin >> temp;
BiTree tree;
tree.Create(temp);
tree.Show();
}
return 0;
}
