- 题目描述：
-
输入一个二叉树，输出其镜像。
- 输入：
-
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n(0<=n<=1000,n代表将要输入的二叉树节点的个数（节点从1开始编号）。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行，每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子，紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子，紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子，紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。
- 输出：
-
对应每个测试案例，
按照前序输出其孩子节点的元素值。
若为空输出NULL。
- 样例输入：
-
7 8 6 10 5 7 9 11 d 2 3 d 4 5 d 6 7 z z z z
- 样例输出：
-
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: 1521User: lcyvinoLanguage: C++Result: AcceptedTime:0 msMemory: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: 1521User: lcyvinoLanguage: C++Result: Wrong Answer ****************************************************************/
