以二叉链表作为二叉树的存储结构，编写程序实现：交换二叉树每个结点的左子树和右子树。以先序遍历构建一棵二叉树，输出中序遍历结果，交换每个节点的左右子树后，输出中序遍历结果。
输入格式:
输入一行字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。
输出格式:
第一行是原二叉树的中序遍历序列；
第二行是交换后的二叉树的中序遍历序列。
输入样例:
在这里给出一组输入。例如：
AB#CD###E#F##
输出样例:
在这里给出相应的输出。例如：
BDCAEF
FEACDB#include<iostream>
using namespace std;
typedef struct BNode
{
char Date;
struct BNode *lchild,*rchild;
}BNode,*BTree;
void PreCreate(BTree &T)
{//先序遍历创建二叉树
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else
{
T=new BNode;
T->Date=ch;
PreCreate(T->lchild);
PreCreate(T->rchild);
}
}
void InTraverse(BTree T,string &str)
{//中序遍历输出二叉树
if(T)//非空树
{
InTraverse(T->lchild,str);
cout<<T->Date;
str+=T->Date;//将输出结果存入str中
InTraverse(T->rchild,str);
}
}
//找到规律：交换前后二叉树中序遍历输出刚好相反
int main()
{
BTree T;
string str;//用来存中序遍历输出的结果
PreCreate(T);
InTraverse(T,str);
cout<<endl;
for(int i=str.length()-1;i>=0;--i)
cout<<str[i];
return 0;
}