所谓二叉树的镜像树就是把一个节点下的左右孩子交换，例如： 下面这棵树是一颗深度为3的完全二叉树

它的镜像就应该是

这个问题其实不难，主要是要将树建立起来，然后把左右节点交换就可以啦

由于输入的数据的格式是

(A(B(D)(E))(C(F)))这种形式，（就是上面的第一颗二叉树的结构）我们需要解析字符串然后建立一棵树（这算一个比较麻烦的事吧，对于我刚刚接触这块）

我的想法就是利用栈来做这个问题。 第一步：初始化一个树结构的指针栈，读取第一个括号，然后初始化一个根节点，并压入栈 第二步：开始读取字符串（字符串是绝对正确的），当遇到‘（’的时候就初始化一个子节点，压入栈， 第三步：判断应该把这个节点添加到那个位置，其实就是取得栈里面的栈顶元素，判断它的左右孩子空不空，优先左，其次右。 第四步：遇到‘）’直接把当前的节点指针从栈里面弹掉。 循环的条件就是在字符串不到‘\0’

具体的贴代码：

#include <stdio.h>
#include <stack>
#include <stdlib.h>
#include <iostream>
using namespace std;
//二叉树的节点结构
typedef struct Node{
int data;
struct Node *Lchild;
struct Node *Rchild;
}Node,*Tree;
//把数据转化为树
Tree initTree(char *str){
stack<Tree> s;
stack<char> c;
Tree T,t,temp;
//创建根节点
c.push(*str);
str++;
T=(Node *)malloc(sizeof(Node));
T->data=*str;
T->Lchild=NULL;
T->Rchild=NULL;
s.push(T);
str++;
//创建各节点间的关系
while(*str){
if(*str=='('){
c.push('c');
temp=(Node )malloc(sizeof(Node));
temp->data=(++str);
temp->Lchild=NULL;
temp->Rchild=NULL;
t=s.top();//取得父节点
if(t->Lchild==NULL)
t->Lchild=temp;
else
t->Rchild=temp;
s.push(temp);
}
else if(*str==')'){
s.pop();
c.pop();
}
str++;
}
return T;
}
//先序遍历，属于二叉树的基本操作
void Preorder(Tree T){
if(T){
printf("%c ",T->data);
Preorder(T->Lchild);
Preorder(T->Rchild);
}
}
/*这个就是二叉树的镜像转换函数，其实很简单
和交换变量的值一样的做法
*/
void convert(Tree T){
if(NULL==T)
return;
Tree temp=T->Lchild;//临时节点
T->Lchild=T->Rchild;
T->Rchild=temp;
//递归操作
convert(T->Lchild);
convert(T->Rchild);
}
int main(){
freopen("test.in","r",stdin);
char str[200];
char *s=str;
Tree T;
while(scanf("%s",str)!=EOF){
T=initTree(s);
convert(T);
Preorder(T);
cout<<endl;
}
return 0;
}