交换二叉树每个结点的左孩子和右孩子

以二叉链表作为二叉树的存储结构，编写程序实现：交换二叉树每个结点的左子树和右子树。以先序遍历构建一棵二叉树，输出中序遍历结果，交换每个节点的左右子树后，输出中序遍历结果。

输入格式:

输入一行字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:

第一行是原二叉树的中序遍历序列；

第二行是交换后的二叉树的中序遍历序列。

输入样例:

在这里给出一组输入。例如：

AB#CD###E#F##

输出样例:

在这里给出相应的输出。例如：

BDCAEF
FEACDB
源代码

#include<iostream>
#include<string>
using namespace std;
typedef struct node{
char ch;
node *lc,*rc;
}node,*Node;
string s;
int len;

void build(Node& p,int& k){
if(s[k]=='#'){
k++;
p=NULL;
return;
}
p=new node();
p->ch=s[k++];
build(p->lc,k);
build(p->rc,k);
}

void mid_show(Node p){
if(p==NULL) return;
mid_show(p->lc);
cout<<p->ch;
mid_show(p->rc);
}

void exchange(Node p){
if(p==NULL) return;
Node t=p->lc;
p->lc=p->rc;
p->rc=t;
exchange(p->lc);
exchange(p->rc);
}
int main(){
getline(cin,s);
len=s.size();

Node p=NULL;
int k=0;
build(p,k);

mid_show(p);
cout<<endl;

exchange(p);
mid_show(p);

return 0;
}