本文共 3152 字，大约阅读时间需要 10 分钟。
原文链接：http://ac.jobdu.com/problem.php?pid=1521
题目1521：二叉树的镜像
输入一个二叉树，输出其镜像。
输入可能包含多个测试样例，输入以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
1、前序遍历树上每一个节点
2、如果该节点有子节点，则交换左右子节点
提交OJ时注意：
若有字符输入，必须先清理输入缓冲区，只有一个getchar（）是不够的！！！！正确写法如下：
while((ch = getchar()) != '\n');
#include#include bool flag = true;//标记当前节点为根节点struct treeNode{ int data; treeNode *left; treeNode *right;};//前序遍历-交换非叶子节点的左右节点
void mirror(treeNode *root){ if(root == NULL) return; if(root->left != NULL || root->right != NULL){ treeNode *temp = root->left; root->left = root->right; root->right = temp; } if(root->left != NULL) mirror(root->left); if(root->right != NULL) mirror(root->right); return;}/* i - 序号为i的节点 tree[i][0] - i节点的值 tree[i][1] - i节点左子节点的序号 tree[i][2] - i节点右子节点的序号 */ treeNode * createTree(int tree[1000][3], int i){ treeNode *root = (treeNode *)malloc(sizeof(treeNode)); root->data = tree[i][0]; if(tree[i][1] != 0){ int indleft = tree[i][1]; root->left = createTree(tree, indleft - 1); } else root->left = NULL; if(tree[i][2] != 0){ int indright = tree[i][2]; root->right = createTree(tree, indright - 1); } else root->right = NULL; return root;}void print(treeNode *root){ if(root == NULL) return; if(flag){ printf("%d", root->data); flag = false; } else printf(" %d", root->data); if(root->left != NULL) print(root->left); if(root->right != NULL) print(root->right); return;}int main(){ int n; int tree[1000][3]; while(scanf("%d", &n) != EOF){ flag = true; if(n == 0){ printf("NULL\n"); continue; } for(int i = 0; i < 1000; i ++){ tree[i][0] = 0; tree[i][1] = 0; tree[i][2] = 0; } for(int i = 0; i < n; i ++) scanf("%d", &tree[i][0]); char ch; int l; int r; for(int i = 0; i < n; i ++){ while((ch = getchar()) != '\n');//特别注意！！！！！ scanf("%c", &ch); if(ch == 'd'){ scanf("%d %d", &l, &r); tree[i][1] = l; tree[i][2] = r; } else if(ch == 'l'){ scanf("%d", &l); tree[i][1] = l; } else if(ch == 'r'){ scanf("%d", &r); tree[i][2] = r; } } treeNode *root = createTree(tree, 0); mirror(root); print(root); printf("\n"); } return 0;}/************************************************************** Problem: 1521 Language: C++ Result: Accepted Time:0 ms Memory:1020 kb****************************************************************/ 转载地址：http://fesob.baihongyu.com/