一：題目

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

fig1.jpg
圖1

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

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

輸出格式:
如果兩棵樹是同構(gòu)的，輸出“Yes”，否則輸出“No”。

輸入樣例1（對應圖1）：

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

輸出樣例1:

Yes

輸入樣例2（對應圖2）：

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

輸出樣例2:

No

二：思路

思路：先建樹，建完樹后進行判斷
判斷是否同構(gòu)的依據(jù)：
1.判斷根結(jié)點是否為空，若兩個根結(jié)點都為空則是同構(gòu)樹；如果一個為空一個不為空則不是同構(gòu)樹
2.兩個根結(jié)點都存在，但是對應的數(shù)值不同，不是同構(gòu)樹
3.判斷兩個根結(jié)點的左右子樹是否相同（用遞歸進行判斷）

三：上碼

/**思路：先建樹，建完樹后進行判斷 判斷是否同構(gòu)的依據(jù)：1.判斷根結(jié)點是否為空，若兩個根結(jié)點都為空則是同構(gòu)樹；如果一個為空一個不為空則不是同構(gòu)樹2.兩個根結(jié)點都存在，但是對應的數(shù)值不同，不是同構(gòu)樹3.判斷兩個根結(jié)點的左右子樹是否相同（用遞歸進行判斷） */ #include<bits/stdc++.h> using namespace std;typedef struct Node* Ptr; struct Node{char data;int left;int right; }tree1[20],tree2[20];int createTree(struct Node tree[]){int N;cin >> N;int sonRoot[200] = {0}; //記錄那些結(jié)點作為子結(jié)點出現(xiàn) for(int i = 0; i < N; i++){char a,b,c;cin >> a >> b >> c;tree[i].data = a;if(b != '-'){tree[i].left = b - '0';//將char類型轉(zhuǎn)換成int類型sonRoot[b - '0'] = 1; }else{tree[i].left = -1;//空樹賦值為-1 }if(c != '-'){tree[i].right = c - '0';sonRoot[c - '0'] = 1;}else{tree[i].right = -1;} }int root = -1;//初始化根節(jié)點for(int i = 0; i < N; i++){if(sonRoot[i] == 0){//除了根節(jié)點 其他都已經(jīng)賦值為 1 root = i;}} return root; }bool judge(int root1,int root2){if(root1 == -1 && root2 == -1){return true;}else if( root1 == -1 && root2 != -1 || root1 != -1 && root2 == -1){return false;}else if(tree1[root1].data != tree2[root2].data){//倆個跟結(jié)點都存在，但數(shù)值不同 return false; }else if (tree1[tree1[root1].left].data == tree2[tree2[root2].left].data) {//如果左子樹的值相等則判斷右子樹return judge(tree1[root1].right, tree2[root2].right);}else {//否則判斷是否第二棵樹是在第一課樹左右子樹調(diào)換之后得到的return judge(tree1[root1].left, tree2[root2].right)&& judge(tree1[root1].right, tree2[root2].left);} } int main(){int root1 = createTree(tree1);int root2 = createTree(tree2);if(judge(root1,root2)){cout << "Yes";}else{cout << "No";}}

四：總結(jié)

這個碼不是我自己寫了，感覺好難，我是參考別人的！！！！！！!！！！！！！！！ 加油Boby!!!

總結(jié)

以上是生活随笔為你收集整理的7-3 树的同构 (25 分)(思路加详解)来呀baby!!!!!!!!的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。