对称二叉树
【问题描述】
如果二叉树的左右子树的结构是对称的,即两棵子树皆为空,或者皆不空,则称该二叉树是对称的。编程判断给定的二叉树是否对称.
例:如下图中的二叉树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 }
测试数据:
abc##de#####fg No a Yes abcd No abcdefg Yes ABC#D#E No