剑指OFFER之二叉树的镜像（九度OJ1521）

题目描述：

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

输入：

输入可能包含多个测试样例，输入以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

解题思路：

　　通常的思路，我们创建一个树以后，交换没个节点的左右孩子就行了。

　　但是对于这道题，还有个思路，我们创建自己的数据结构，使得数据存储在一个数组中，这个数组的元素是一个树的节点，这样就省去了再创建树的过程。

#define MAX 1000

typedef struct treeElement{
    int flag;//用于判断数组中有没有元素，有元素的数组元素被初始化为1
    int num;
    int lchild;//左孩子的下标值
    int rchild;
}TreeElement;
typedef struct treeArr{
    TreeElement tree[MAX];
}TreeArr;

　　在数据结构使用前，记得要进行初始化

for(i=0;i<MAX;i++){
            t->tree[i].flag =0;
            t->tree[i].num = 0;
            t->tree[i].lchild = 0;
            t->tree[i].rchild = 0;
        }

　　然后，对于一个树，如果正常前序遍历，是它自己的树。而如果按照中右左的顺序扫描树，得到的就是它的镜像的前序遍历了。这样即节省了空间，又节省了交换的时间。

代码：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <memory.h>
 4 #define MAX 1000
 5 int nullTree = 0;
 6 typedef struct treeElement{
 7     int flag;
 8     int num;
 9     int lchild;
10     int rchild;
11 }TreeElement;
12 typedef struct treeArr{
13     TreeElement tree[MAX];
14 }TreeArr;
15  
16 void printfTree(TreeArr *t);
17 void printNode(TreeArr *t,TreeElement *te);
18 int main(){
19     TreeArr *t = (TreeArr *)malloc(sizeof(TreeArr));
20     int n;
21     char c;
22     while(scanf("%d",&n)!=EOF && n>=0 && n<=1000){
23         nullTree = 0;
24         int i,n1,n2;
25         if(n != 0)
26             nullTree = 1;
27         for(i=0;i<MAX;i++){
28             t->tree[i].flag =0;
29             t->tree[i].num = 0;
30             t->tree[i].lchild = 0;
31             t->tree[i].rchild = 0;
32         }
33          
34         for(i=1;i<=n;i++){
35             scanf("%d",&t->tree[i].num);
36             t->tree[i].flag = 1;
37             t->tree[i].lchild = 0;
38             t->tree[i].rchild = 0;
39         }
40         for(i=1;i<=n;i++){
41             scanf("
%c",&c);
42             if(c == 'd'){
43                      scanf("%d %d",&n1,&n2);
44                      t->tree[i].lchild = n1;
45                      t->tree[i].rchild = n2;
46                      getchar();
47             }
48             if(c == 'l'){
49                     scanf("%d",&n1);
50                     t->tree[i].lchild = n1;
51                      getchar();
52             }
53             if(c == 'r'){
54                      scanf("%d",&n1);
55                      t->tree[i].rchild = n1;
56                       getchar();
57             }
58             if(c == 'z'){
59                      getchar();
60             }
61         }
62         printfTree(t);
63         printf("
");
64     }
65     return 0;
66 }
67 void printfTree(TreeArr *t){
68     if(nullTree)
69         printNode(t,&t->tree[1]);
70     else
71         printf("NULL");
72 }
73 void printNode(TreeArr *t,TreeElement *te){
74     if(!te->flag)
75         return;
76     else{
77         if(te->num == t->tree[1].num)
78             printf("%d",te->num);
79         else
80             printf(" %d",te->num);
81         if(te->rchild)
82             printNode(t,&t->tree[te->rchild]);
83         if(te->lchild)
84             printNode(t,&t->tree[te->lchild]);
85         return ;
86     }
87 }
88 /**************************************************************
89     Problem: 1521
90     User: xhalo
91     Language: C
92     Result: Accepted
93     Time:0 ms
94     Memory:916 kb
95 ****************************************************************/