首页 > > 程序设计 > C/C++ >

对称二叉树

2018-06-17 22:55:49来源：未知阅读 ()

对称二叉树

【问题描述】

如果二叉树的左右子树的结构是对称的，即两棵子树皆为空，或者皆不空，则称该二叉树是对称的。编程判断给定的二叉树是否对称.

例：如下图中的二叉树T1是对称的，T2是不对称的。

二叉树用顺序结构给出，若读到#则为空，二叉树T1=ABCDE，T2=ABCD#E，如果二叉树是对称的，输出“Yes”,反之输出“No”。

【输入样例】tree_c.in

　　　ABCDE

【输出样例】tree_c.out

　　　Yes

 1 #include<iostream>
 2 using namespace std;
 3 struct node
 4 {
 5     int parent;
 6     int lchild;
 7     int rchild;
 8 }a[1001];
 9 int main()
10 {
11     char d;
12     int i=1;
13     while(cin>>d)
14     {
15         if(d=='#')
16         {
17             a[i/2].lchild=0;
18             a[i].parent=0;
19         }
20         else
21         {
22             if(i%2==0)
23             {
24                 a[i/2].lchild=d;
25                 a[i].parent=i/2;
26             }
27             else
28             {
29                 a[i/2].rchild=d;
30                 a[i].parent=i/2;
31             }
32         }
33         i++;
34     }
35     int flag=0;
36     for(int j=1;j<=i;j++)
37     {
38         if((a[j].lchild!=0&&a[j].rchild!=0)||(a[j].lchild==0&&a[j].rchild==0))
39         {
40             continue;
41         }
42         else
43         {
44             flag=1;
45             break;
46         }
47     }
48     if(flag==1)
49     {
50         cout<<"No";
51     }
52     else
53     {
54         cout<<"Yes";
55     }
56     return 0;
57 }