团体程序设计天梯赛 L3-016. 二叉搜索树的结构

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <string.h>
  4 #include <math.h>
  5 #include <stdbool.h>
  6 #include <algorithm>
  7 using namespace std;
  8 #define maxn 500+100
  9 
 10 //离散化+结构体数组存储树(数据可能很大，不可能用tree[x]记录值为x的结点，而用链表存储树，在这一题判断兄弟结点等不太方便)
 11 //输入的数据点也许并不在树上
 12 //兄弟结点不能相同
 13 
 14 struct node
 15 {
 16     long left,right,fa,depth;
 17 }tree[maxn];
 18 
 19 long n,num[maxn],z[maxn];
 20 
 21 bool cmp(long a,long b)
 22 {
 23     return a<b;
 24 }
 25 
 26 //better:binary search
 27 int findnum(long value)
 28 {
 29     long i;
 30     for (i=1;i<=n;i++)
 31         if (value==z[i])
 32             return i;
 33     return n+1;
 34 }
 35 
 36 int add(long pos,long value,long depth)
 37 {
 38     if (value < pos)
 39     {
 40         if (tree[pos].left==0)
 41         {    
 42             tree[pos].left=value;
 43             tree[value].fa=pos;
 44             tree[value].depth=depth;
 45         }
 46         else
 47             add(tree[pos].left,value,depth+1);
 48     }
 49     else
 50     {
 51         if (tree[pos].right==0)
 52         {
 53             tree[pos].right=value;
 54             tree[value].fa=pos;
 55             tree[value].depth=depth;
 56         }
 57         else
 58             add(tree[pos].right,value,depth+1);
 59     }
 60 }
 61 
 62 int main()
 63 {
 64     long i,j,x,y,p,q,m,root;
 65     char a[20],b[20],c[20],d[20],e[20],f[20];
 66     scanf("%ld",&n);
 67     for (i=1;i<=n;i++)
 68     {
 69         scanf("%ld",&z[i]);
 70         num[i]=z[i];
 71     }
 72     for (i=1;i<=n;i++)
 73     {
 74         tree[i].left=0;
 75         tree[i].right=0;
 76         tree[i].fa=0; //不能像并查集一样设置为i 
 77     }
 78     sort(z+1,z+n+1,cmp); //[x,y)
 79     
 80     root=findnum(num[1]);
 81     tree[root].depth=0;
 82     for (i=2;i<=n;i++)
 83     {
 84         j=findnum(num[i]);
 85         add(root,j,1);
 86     }
 87 
 88     scanf("%ld",&m);
 89     while (m)
 90     {
 91         m--;
 92         scanf("%ld",&x);
 93         p=findnum(x);
 94         scanf("%s",a);
 95         if (strcmp(a,"is")==0)
 96         {
 97             scanf("%s%s",b,c);
 98             if (strcmp(c,"root")==0)
 99             {
100 //                if (p!=n+1 && tree[p].fa==0)
101                 if (x==num[1])
102                     printf("Yes
");
103                 else
104                     printf("No
");
105             }
106             else if (strcmp(c,"parent")==0)
107             {
108                 scanf("%s",d);
109                 scanf("%ld",&y);
110                 q=findnum(y);
111                 if (q!=n+1 && tree[q].fa==p)
112                     printf("Yes
");
113                 else
114                     printf("No
");
115             }
116             else if (strcmp(c,"left")==0)
117             {
118                 scanf("%s%s",d,e);
119                 scanf("%ld",&y);
120                 q=findnum(y);
121                 if (q!=n+1 && tree[q].left==p)
122                     printf("Yes
");
123                 else
124                     printf("No
");                
125             }
126             else
127             {
128                 scanf("%s%s",d,e);
129                 scanf("%ld",&y);
130                 q=findnum(y);
131                 if (q!=n+1 && tree[q].right==p)
132                     printf("Yes
");
133                 else
134                     printf("No
");                    
135             }
136         }
137         //and
138         else
139         {
140             scanf("%ld",&y);
141             q=findnum(y);
142             scanf("%s%s",b,c);
143             if (strcmp(c,"siblings")==0)
144             {
145                 if (p!=n+1 && q!=n+1  && p!=q && tree[p].fa==tree[q].fa) //两个结点不能相同
146                     printf("Yes
");
147                 else
148                     printf("No
");
149             }
150             else
151             {
152                 scanf("%s%s%s",d,e,f);
153                 if (p!=n+1 && q!=n+1 && tree[p].depth==tree[q].depth)
154                     printf("Yes
");
155                 else
156                     printf("No
");
157             }
158         }
159     }
160     return 0;
161 }