首页 > 代码库 > 剑指OFFER之二叉树的镜像(九度OJ1521)

剑指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("\n%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("\n");
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 ****************************************************************/