數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)之二叉樹一：樹的同構(gòu)

PRoblem Description

給定兩棵樹T1和T2。如果T1可以通過若干次左右孩子互換就變成T2，則我們稱兩棵樹是“同構(gòu)”的。例如圖1給出的兩棵樹就是同構(gòu)的，因?yàn)槲覀儼哑渲幸豢脴涞慕Y(jié)點(diǎn)A、B、G的左右孩子互換后，就得到另外一棵樹。而圖2就不是同構(gòu)的。

圖1

圖2

現(xiàn)給定兩棵樹，請(qǐng)你判斷它們是否是同構(gòu)的。

Input

Output

Example Input

8A 1 2B 3 4C 5 -D - -E 6 -G 7 -F - -H - -8G - 4B 7 6F - -A 5 1H - -C 0 -D - -E 2 -
Example Output
Yes
Hint
測(cè)試數(shù)據(jù)對(duì)應(yīng)圖1 
Author
 xam 
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#include<iostream>using namespace std;typedef struct node//建立以三個(gè)數(shù)組建立形成的樹{    char data;    int l;    int r;}tree;tree T1[10],T2[10];int build(tree T[], int n)//將題目數(shù)據(jù)建立樹{    int root = -1;    char cl,cr,a[10],b[10],c[10];    int check[10] = {0};//標(biāo)記，并尋找根    if(n)    {       for(int i=0;i<n;i++)       {           scanf("%s%s%s",a,b,c);           T[i].data = a[0];           cl = b[0];           cr = c[0];           if(cl!='-')           {             T[i].l = cl-48;             check[T[i].l] = 1;//           }           else             T[i].l = -1;             if(cr!='-')             {                T[i].r = cr-48;                check[T[i].r] = 1;             }             else T[i].r = -1;       }       for(int i=0;i<n;i++)       {          if(!check[i])          {             root = i;             break;          }       }    }  return root;}int cmp(int r1,int r2)//遞歸查找左右是否相等{ //前三個(gè)判斷均比較的是當(dāng)前情況   if((r1==-1)&&(r2==-1))//遞歸到葉子時(shí)，返回   return 1;   if((r1==-1&&r2!=-1)||(r1!=-1&&r2==-1))//數(shù)據(jù)不相等或結(jié)構(gòu)不對(duì)稱時(shí)退出   return 0;   if(T1[r1].data!=T2[r2].data)    return 0;    if(T1[r1].l==-1&&T2[r2].l==-1)//左節(jié)點(diǎn)不存在時(shí)，處理右節(jié)點(diǎn)      return cmp(T1[r1].r,T2[r2].r);    if(T1[r1].l!=-1&&T2[r2].l!=-1   //左節(jié)點(diǎn)存在且相等時(shí)，對(duì)應(yīng)比較    &&T1[T1[r1].l].data==T2[T2[r2].l].data)    return (cmp(T1[r1].l, T2[r2].l)//遞歸比較下一層    &&cmp(T1[r1].r, T2[r2].r));  else return (cmp(T1[r1].r, T2[r2].l)//其余情況，交換比較，直到遞歸出口結(jié)束  &&cmp(T1[r1].l, T2[r2].r));}int main(){  int n,m;  int r1,r2;  while(~scanf("%d",&n))  {     r1 = build(T1,n);     scanf("%d",&m);     r2 = build(T2,m);     if(cmp(r1,r2))       printf("Yes/n");    else    printf("No/n");  }return 0;}/***************************************************User name: jk160505徐紅博Result: AcceptedTake time: 0msTake Memory: 152KBSubmit time: 2017-02-07 19:48:57****************************************************/