数据结构-1 03-树1 树的同构

  1 #include<stdio.h>
  2 struct node{
  3     char data;
  4     int left,right;
  5 };
  6 struct node a[11],b[11];
  7 int Na,Nb,ra,rb,flag;
  8 int read(struct node a[],int n);
  9 void detect(int a1,int b1);
 10 int main(){
 11     char data;
 12     flag = 1;
 13     scanf("%d",&Na);
 14     if(Na!=0) ra = read(a,Na);
 15     scanf("%d",&Nb);
 16     if(Nb!=0) rb = read(b,Nb);
 17     
 18     if(Na==0&&Nb==0) flag=1;
 19     else if((Na==0&&Nb!=0)||(Na!=0&&Nb==0)) flag=0;
 20     else{
 21         if(Na==Nb) detect(ra,rb);
 22         else flag=0;    
 23     }
 24     
 25     if(flag==1) printf("Yes\n");
 26     else printf("No\n");
 27     return 0;
 28 } 
 29 
 30 int read(struct node a[],int n){
 31     int i;
 32     int root[11];
 33     char data,left,right;
 34     for(i=0;i<n;i++) root[i] = 1;
 35     
 36     for(i=0;i<n;i++){
 37         scanf("%c",&data);
 38         scanf("%c %c %c",&data,&left,&right);
 39         a[i].data = data;
 40         
 41         if(left==‘-‘) a[i].left = -1;
 42         else {
 43             a[i].left = left-‘0‘;
 44             root[a[i].left] = 0;
 45         }
 46     
 47         if(right==‘-‘) a[i].right=-1;
 48         else{
 49             a[i].right = right-‘0‘;
 50             root[a[i].right] = 0;
 51         }    
 52     }
 53     
 54     for(i=0;i<n;i++){
 55         if(root[i]==1) break;
 56     }
 57     return i;
 58 }
 59 
 60 void detect(int a1,int b1){
 61     int lefta,righta,leftb,rightb;
 62     if(a[a1].data==b[b1].data){
 63         lefta = a[a1].left;
 64         righta = a[a1].right;
 65         leftb = b[b1].left;
 66         rightb = b[b1].right;
 67         
 68         if(lefta!=-1&&righta!=-1){
 69             if(leftb!=-1&&rightb!=-1){
 70                 //都不为空子树
 71                  if(a[lefta].data==b[leftb].data&&a[righta].data==b[rightb].data) {
 72                      detect(lefta,leftb);
 73                      detect(righta,rightb);
 74                  }
 75                  else if(a[lefta].data==b[rightb].data&&a[righta].data==b[leftb].data){
 76                      detect(lefta,rightb);
 77                      detect(righta,leftb);
 78                  }
 79                  else{
 80                      //printf("NO\n");
 81                      if(flag==1) flag=0;
 82                      return;
 83                  }
 84             }
 85             else{
 86             //    printf("NO\n");
 87             if(flag==1) flag=0;
 88                 return;
 89             }
 90         }
 91         else if(lefta!=-1 && righta==-1){
 92             if(righta==rightb) {
 93                 if(a[lefta].data==b[leftb].data) detect(lefta,leftb);
 94             }
 95             else if(righta==leftb){
 96                 if(a[lefta].data==b[righta].data) detect(lefta,rightb);
 97             }
 98             else{
 99                 //printf("NO\n");
100                 if(flag==1) flag=0;
101                 return ;
102             }
103         }
104         else if(lefta==-1&&righta!=-1){
105             if(lefta==leftb){
106                 if(a[righta].data==b[rightb].data) return;
107                 else{
108                     //printf("NO\n");
109                     if(flag==1) flag=0;
110                     return;
111                 }
112             }
113             else if(lefta==rightb){
114                 if(a[righta].data==b[lefta].data) return;
115                 else{
116                     //printf("NO\n");
117                     if(flag==1) flag=0;
118                     return;
119                 }
120             }
121             else{
122                 //printf("NO\n");
123                 if(flag==1) flag=0;
124                 return;
125             }
126         }
127         else return;
128     }
129     else{
130             //printf("NO\n");
131             if(flag==1) flag=0;
132             return;
133         
134     }
135     
136 }