樹的同構

給定兩棵樹T1和T2。如果T1可以通過若干次左右孩子互換就變成T2,則我們稱兩棵樹是“同構”的。例如圖1給出的兩棵樹就是同構的,因為我們把其中一棵樹的結點A、B、G的左右孩子互換后,就得到另外一棵樹。而圖2就不是同構的。

圖1

圖2

現給定兩棵樹,請你判斷它們是否是同構的。

輸入格式:

輸入給出2棵二叉樹樹的信息。對于每棵樹,首先在一行中給出一個非負整數N(≤),即該樹的結點數(此時假設結點從0到N−1編號);隨后N行,第i行對應編號第i個結點,給出該結點中存儲的1個英文大寫字母、其左孩子結點的編號、右孩子結點的編號。如果孩子結點為空,則在相應位置上給出“-”。給出的數據間用一個空格分隔。注意:題目保證每個結點中存儲的字母是不同的。

輸出格式:

如果兩棵樹是同構的,輸出“Yes”,否則輸出“No”。

輸入樣例1(對應圖1):

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 -

輸出樣例1:

Yes

輸入樣例2(對應圖2):

8B 5 7F - -A 0 3C 6 -H - -D - -G 4 -E 1 -8D 6 -B 5 -E - -H - -C 0 2G - 3F - -A 1 4

輸出樣例2:

No
算法實現及思路

#include <stdio.h>#define MaxTree 10#define ElementType char#define Tree int#define Null -1//定義二叉樹的結點//采用結構數組存儲二叉樹struct TreeNode{ElementType Element;Tree left;Tree right;}T1[MaxTree],T2[MaxTree];int check[MaxTree];//check數組用來檢查誰是根節點//建樹函數Tree BuildTree(struct TreeNode T[]){int N,i;Tree Root=Null;char cl,cr;scanf("%d\n",&N);if(N){for(i=0;i<N;i++) check[i]=0;//初始check數組全部置0for(i=0;i<N;i++){scanf("%c %c %c\n", &T[i].Element,&cl,&cr);if(cl!='-'){T[i].left=cl-'0';check[T[i].left]=1;//指向的結點check值設置為1}else{T[i].left=Null;//若結點指向為空,則將left設置為-1}// 右結點同理if(cr!='-'){T[i].right=cr-'0';check[T[i].right]=1;}else{T[i].right=Null;}}for(i=0;i<N;i++){//若沒有任何結點指向的那一個結點 就是該樹的根節點if(!check[i]) break;}Root =i;//值賦給根并返回}return Root;}//遞歸比較左右結點是否相等,若兩結點相等int lsomorphic(Tree R1,Tree R2){//比較是否兩棵樹是否同構if((R1==Null)&&(R2==Null))//若同為空結點,返回1return 1;if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))//若 一個空,一個不空,肯定不同構,返回0return 0;if(T1[R1].Element!=T2[R2].Element)//若兩結點不空,但是值不相等,肯定不同構,返回0return 0;if((T1[R1].left==Null)&&(T2[R2].left==Null))//若兩棵樹的結點都沒有左子樹,則比較右子樹return lsomorphic(T1[R1].right,T2[R2].right);//若兩棵樹的當前左結點相等,遞歸比較左右子結點if(((T1[R1].left!=Null)&&(T2[R2].left!=Null))&&((T1[T1[R1].left].Element)==(T2[T2[R2].left].Element)))return (lsomorphic(T1[R1].left,T2[R2].left)&&lsomorphic(T1[R1].right,T2[R2].right) );else//若左右子結點互換同構,則互換比較return (lsomorphic(T1[R1].left,T2[R2].right)&&lsomorphic(T1[R1].right,T2[R2].left));
}int main(){ Tree R1,R2; R1=BuildTree(T1); R2=BuildTree(T2); if(lsomorphic(R1,R2)) printf("Yes\n"); else printf("No\n"); return 0;
}