【问题描述】
给定扩展二叉树的前序序列，构建二叉树。
求这课二叉树的镜像，并输出其前序遍历序列。
【输入形式】
输入扩展二叉树的前序序列。
【输出形式】
输出镜像二叉树的前序遍历序列。
【样例输入】
ab##cd##e##
【样例输出】
镜像后二叉树的前序遍历序列是：acedb
【样例说明】
上述输入对应以下结构的二叉树：
a
/
b c/
d e二叉树的镜像如下图
a
/
c b/
e d
【代码】
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX = 1000;
struct BiNode
{
char data;//数据域
BiNode* lchild, * rchild;//左右儿子指针
};
class BiTree {
private:
BiNode* root;
public:
BiTree() { root = creat(root); }
~BiTree() {
release(root);
}
BiNode* getRoot() { return root; }
BiNode* creat(BiNode* bt); //构造函数调用
void release(BiNode* bt); //析构函数调用，释放树的存储空间
void Mirror(BiNode* pRoot);//镜像
void preOrder(BiNode* bt);//前序输出
};
BiNode* BiTree::creat(BiNode* bt)
{
char ch;
cin >> ch;
if (ch == '#')
bt = NULL;
else
{
bt = new BiNode;
bt->data = ch;
bt->lchild = creat(bt->lchild);
bt->rchild = creat(bt->rchild);
}
return bt;
}
void BiTree::release(BiNode* bt)
{
if (bt != NULL)
{
release(bt->lchild);
release(bt->rchild);
delete bt;
}
}
//镜像
void BiTree::Mirror(BiNode* bt)
{
if (bt == nullptr)
return;
swap(bt->lchild, bt->rchild);//交换左右子树
Mirror(bt->lchild);
Mirror(bt->rchild);
}
void BiTree::preOrder(BiNode* bt)
{
if (bt == NULL)
{
return;
}
cout << bt->data;
preOrder(bt->lchild);
preOrder(bt->rchild);
}
int main()
{
BiTree tree;
tree.Mirror(tree.getRoot());
cout << "镜像后二叉树的前序遍历序列是：";
tree.preOrder(tree.getRoot());
return 0;
}
