题目描述：

输入一个二叉树，输出其镜像。

 

输入：

输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n(0<=n<=1000,n代表将要输入的二叉树节点的个数（节点从1开始编号）。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行，每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子，紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子，紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子，紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。

 

输出：

对应每个测试案例，
按照前序输出其孩子节点的元素值。
若为空输出NULL。

 

样例输入：

78 6 10 5 7 9 11d 2 3d 4 5d 6 7zzzz

样例输出：

8 10 11 9 6 7 5

Code:

#include <iostream>#include <cstdio> using namespace std; struct BinaryTreeNode{    int data;    int lchild;    int rchild;}; void exchangeNode(BinaryTreeNode arr[],int current,int n){    if(current==0)    //结点为空        return;    if(current>n)        return;    if(arr[current].lchild==0&&arr[current].rchild==0)   //叶子节点        return;    int tmp=arr[current].lchild;    arr[current].lchild=arr[current].rchild;    arr[current].rchild=tmp;    if(arr[current].lchild!=0)        exchangeNode(arr,arr[current].lchild,n);    if(arr[current].rchild!=0)        exchangeNode(arr,arr[current].rchild,n);} bool isFirst;void preOrder(BinaryTreeNode arr[],int current){    if(current!=0){        if(isFirst){            cout<<arr[current].data;            isFirst=false;        }else{            cout<<" "<<arr[current].data;        }    }    if(arr[current].lchild!=0)        preOrder(arr,arr[current].lchild);    if(arr[current].rchild!=0)        preOrder(arr,arr[current].rchild);}  int main(){   int n;   const int arrSize=1010;   char operation;   BinaryTreeNode arr[arrSize];   while(cin>>n){        getchar();        if(n==0){            cout<<"NULL\n";            continue;        }        for(int i=1;i<=n;++i){            arr[i].lchild=arr[i].rchild=0;            cin>>arr[i].data;        }        for(int j=1;j<=n;++j){            cin>>operation;            if(operation==‘d‘){                cin>>arr[j].lchild>>arr[j].rchild;            }            if(operation==‘l‘){                cin>>arr[j].lchild;                arr[j].rchild=0;            }            if(operation==‘r‘){                cin>>arr[j].rchild;                arr[j].lchild=0;            }            if(operation==‘z‘){                arr[j].lchild=arr[j].rchild=0;            }        }        isFirst=true;        exchangeNode(arr,1,n);        preOrder(arr,1);        cout<<endl;   }   return 0;} /**************************************************************    Problem: 1521    User: lcyvino    Language: C++    Result: Accepted    Time:0 ms    Memory:1520 kb****************************************************************/

 

贴上之前WA的代码:

#include <cstdio> using namespace std; struct BinaryTreeNode{    int data;    int lchild;    int rchild;}; void exchangeNode(BinaryTreeNode *arr,int index){   //递归交换2个结点    if(index==0)        return;    if(arr[index].lchild==0&&arr[index].rchild==0)        return;    int tmplchild=arr[index].lchild;    arr[index].lchild=arr[index].rchild;    arr[index].rchild=tmplchild;    if(arr[index].lchild!=0){        exchangeNode(arr,arr[index].lchild);    }    if(arr[index].rchild!=0){        exchangeNode(arr,arr[index].rchild);    }} bool flag;  //用来处理输出时的空格 void preOrder(BinaryTreeNode *arr,int index){   //先序遍历    if(index!=0){        if(flag==true){            printf("%d",arr[index].data);            flag=false;        }else{            printf(" %d",arr[index].data);        }        if(arr[index].lchild!=0){            preOrder(arr,arr[index].lchild);        }else{            if(arr[index].lchild==0&&arr[index].rchild!=0){                printf(" NULL");            }        }        if(arr[index].rchild!=0){            preOrder(arr,arr[index].rchild);        }else{            if(arr[index].rchild==0&&arr[index].lchild!=0){                printf(" NULL");            }        }    }} int main(){   int n;   while(scanf("%d",&n)!=EOF){        BinaryTreeNode arr[1010];        char ch;        for(int cnt1=1;cnt1<=n;++cnt1){   //输入值            scanf("%d",&arr[cnt1].data);        }        for(int cnt2=1;cnt2<=n;++cnt2){            getchar();            scanf("%c",&ch);            if(ch==‘d‘){                scanf("%d%d",&arr[cnt2].lchild,&arr[cnt2].rchild);            }            if(ch==‘l‘){                scanf("%d",&arr[cnt2].lchild);                arr[cnt2].rchild=0;            }            if(ch==‘r‘){                scanf("%d",&arr[cnt2].rchild);                arr[cnt2].lchild=0;            }            if(ch==‘z‘){                arr[cnt2].lchild=arr[cnt2].rchild=0;            }        }        exchangeNode(arr,1);        flag=true;        if(n==0){            printf("NULL\n");            continue;        }        preOrder(arr,1);        printf("\n");   }   return 0;} /**************************************************************    Problem: 1521    User: lcyvino    Language: C++    Result: Wrong Answer****************************************************************/

 

 

 

 

剑指OFFER之二叉树的镜像