题目描述

假设二叉树用二叉链表存储，用先序序列结果创建。输入二叉树的先序序列，请你先创建二叉树，并对树做个镜面反转，再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

测试次数t

每组测试数据是一个二叉树的先序遍历序列，#表示空树

输出

对每棵二叉树，输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树，输出四个NULL（后面不加空格）。如下：

NULL

NULL

NULL

NULL

样例输入

样例输出

#include<iostream> 
using namespace std;
class BiTreeNode {
public:
	char data;
	BiTreeNode* leftChild;
	BiTreeNode* RigheChild;
	BiTreeNode() :leftChild(NULL), RigheChild(NULL) {}
	~BiTreeNode() {}
};
class BiTree {
private:
	BiTreeNode* Root;
	int pos;
	string strTree;
	BiTreeNode* CreateBiTree();
	void PreOrder(BiTreeNode* t);
	void InOrder(BiTreeNode* t);
	void PostOrder(BiTreeNode* t);
	void LevelOrder(BiTreeNode* root,int i); 
    int Depth(BiTreeNode* T);
    void Mirror(BiTreeNode* t);
public:
	BiTree() {};
	~BiTree() {};
	void CreateTree(string TreeArray);
	void PreOrder();
	void InOrder();
	void PostOrder();
	void LevelOrder(); 
	void Mirror();
};
void BiTree::CreateTree(string TreeArray) {//建立二叉树 
	pos = 0;
	strTree.assign(TreeArray);
	Root = CreateBiTree();
}
BiTreeNode* BiTree::CreateBiTree()
{
	BiTreeNode* T;
	char ch;
	ch = strTree[pos++];
	if (ch == '#') T = NULL;
	else
	{
		T = new BiTreeNode();
		T->data = ch;
		T->leftChild= CreateBiTree();
		T->RigheChild = CreateBiTree();
	}
	return T;
}
//求二叉树深度
int BiTree::Depth(BiTreeNode* T) 
{
    int m, n;
    if (T == NULL)
        return 0; //如果是空树，深度为0，递归结束
    else
    {
        m = Depth(T->leftChild); //递归计算左子树的深度记为m
        n = Depth(T->RigheChild); //递归计算右子树的深度记为n
        if (m > n)//二叉树的深度为m 与n的较大者加1
            return (m + 1); 
        else
            return (n + 1);
    }
}
//层次遍历序列 
void BiTree::LevelOrder(){
	if(Root==NULL) cout<<"NULL";
	int deep=Depth(Root);
	for(int i=1;i<=deep;i++){
		LevelOrder(Root,i);
	}
}
//层次遍历具体函数 
void BiTree::LevelOrder(BiTreeNode* root,int i){
	if(root==NULL||i==0) return;
	if(i==1){
		cout<<root->data<<" ";
		return;
	}
	LevelOrder(root->leftChild,i-1);
	LevelOrder(root->RigheChild,i-1);
}
//镜面反转内部调用函数 
void BiTree::Mirror(){
	Mirror(Root);
}
//镜面反转外部调用函数
void BiTree::Mirror(BiTreeNode* t)
{
	if (t == NULL)
	{
		return;
	}
	swap(t->leftChild, t->RigheChild);//交换左右子树 
	Mirror(t->leftChild);
	Mirror(t->RigheChild);
}
//先序 
void BiTree::PreOrder()
{
	if(Root==NULL) cout<<"NULL";
	PreOrder(Root);
}
void BiTree::PreOrder(BiTreeNode* t) {
	if (t) {
		cout << t->data<<" ";
		PreOrder(t->leftChild);
		PreOrder(t->RigheChild);
	}
}
//中序 
void BiTree::InOrder()
{
	if(Root==NULL) cout<<"NULL";
	InOrder(Root);
}
void BiTree::InOrder(BiTreeNode* t) {
	if (t) {
		InOrder(t->leftChild);
		cout << t->data<<" ";
		InOrder(t->RigheChild);
	}
}
//后序 
void BiTree::PostOrder()
{
	if(Root==NULL) cout<<"NULL";
	PostOrder(Root);
}
void BiTree::PostOrder(BiTreeNode* t) {
	if (t) {
		PostOrder(t->leftChild);
		PostOrder(t->RigheChild);
		cout << t->data<<" ";
	}
}
int main() {
	int t, i;
	cin >> t;
	for (i = 0; i < t; i++) {
		string s;
		cin >> s;
		BiTree* T = new BiTree();
		T->CreateTree(s);
		T->Mirror();
		T->PreOrder();
		cout << endl;
		T->InOrder();
		cout << endl;
		T->PostOrder();
		cout << endl;
		T->LevelOrder();
		cout << endl; 
	}
	return 0;
}