當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

二十、二叉树的同构

發(fā)布時間：2025/3/21 编程问答 27 豆豆

生活随笔收集整理的這篇文章主要介紹了二十、二叉树的同构小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

二十、二叉樹的同構(gòu)

文章目錄

二十、二叉樹的同構(gòu)
- 題目描述
- 解題思路
- 上機(jī)代碼
- 補(bǔ)充說明

題目描述

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

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

輸入格式：

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

輸出格式：

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

測試輸入期待的輸出時間限制內(nèi)存限制額外進(jìn)程

測試用例 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 -	Yes.	1秒	64M
測試用例 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	No.	1秒	64M
測試用例 3	1 A - - 1 A - -	Yes.	1秒	64M

解題思路

題目已經(jīng)給出了我們判斷同構(gòu)的思路：

T1 可以通過若干次左右孩子互換就變成 T2 ，則稱為同構(gòu)。那么我們判斷：

當(dāng)二叉樹為空時，一定同構(gòu)
當(dāng)二叉樹非空時，遞歸判斷：
- T1 左子樹和 T2 左子樹對應(yīng)相等，T1 右子樹與 T2 右子樹對應(yīng)相等時同構(gòu)
- T1 左子樹與 T2 右子樹對應(yīng)相等，T1 右子樹與 T2 左子樹對應(yīng)相等時同構(gòu)

題目給出的是類似于三元組的結(jié)點(diǎn)信息，無法直接建立二叉樹，因此我們先用 TreeNode 結(jié)構(gòu)將結(jié)點(diǎn)信息讀取，再按照三元組中指示的信息進(jìn)行遞歸建樹。

N≤20，意味著結(jié)點(diǎn)的編號可能會是兩位數(shù)，可以通過字符數(shù)組將編號讀取進(jìn)來，再一位一位地進(jìn)行判斷讀取，這一步要耐心細(xì)致。

vis 數(shù)組用于標(biāo)記三元組，所有非根內(nèi)部結(jié)點(diǎn)和葉子結(jié)點(diǎn)都會被標(biāo)記，而未被標(biāo)記的，則一定是根結(jié)點(diǎn)。通過 vis 數(shù)組的標(biāo)記可以在后面將根結(jié)點(diǎn)篩選出來。

上機(jī)代碼

#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<queue> #include<algorithm> using namespace std; typedef struct NODE {char data;struct NODE *lchild;struct NODE *rchild; }node, *Tree;//三元組 struct TreeNode {char data;int left, right; }q[105]; int vis[1010];//遞歸建樹 Tree CreateTree(Tree T, int n) {T = (Tree)malloc(sizeof(node));T->data = q[n].data;//樹根為AT->lchild = NULL;T->rchild = NULL;if (q[n].left != -1)T->lchild = CreateTree(T->lchild, q[n].left);if (q[n].right != -1)T->rchild = CreateTree(T->rchild, q[n].right);return T; } //判斷同構(gòu) bool Judge(Tree T, Tree Q) {if (T == NULL && Q == NULL)return true;if (T != NULL && Q != NULL){if (T->data == Q->data){if ((Judge(T->lchild, Q->lchild) && Judge(T->rchild, Q->rchild)) || (Judge(T->lchild, Q->rchild) && Judge(T->rchild, Q->lchild)))return true;}elsereturn false;}elsereturn false; } int main() {int n = 0, m = 0;char a[5], b[5], c[5];int flag = 0;//建立第一顆樹Tmemset(vis, 0, sizeof(vis));cin >> n;for (int i = 0; i < n; i++){cin >> a >> b >> c;q[i].data = a[0];if (b[0] == '-')//負(fù)數(shù)q[i].left = -1;else{if (b[1] >= '0'&&b[1] <= '9')//處理兩位數(shù)q[i].left = (b[0] - '0') * 10 + (b[1] - '0');elseq[i].left = b[0] - '0';vis[q[i].left] = 1;//標(biāo)記flag++;}if (c[0] == '-')q[i].right = -1;else{if (c[1] >= '0'&&c[1] <= '9')q[i].right = (c[0] - '0') * 10 + (c[1] - '0');elseq[i].right = c[0] - '0';vis[q[i].right] = 1;flag++;}}Tree T = (Tree)malloc(sizeof(node));T = NULL;if (flag >= n)//不能建樹則跳轉(zhuǎn)，把數(shù)據(jù)讀取即可goto part;if (n != 0) //找到根結(jié)點(diǎn)然后建樹{int root = 0;while (root < n){if (!vis[root])break;root++;}T = CreateTree(T, root);}//建立第二顆樹Qpart:memset(vis, 0, sizeof(vis));cin >> m;for (int i = 0; i < m; i++){cin >> a >> b >> c;q[i].data = a[0];if (b[0] == '-')q[i].left = -1;else{if (b[1] >= '0'&&b[1] <= '9')q[i].left = (b[0] - '0') * 10 + (b[1] - '0');elseq[i].left = b[0] - '0';vis[q[i].left] = 1;}if (c[0] == '-')q[i].right = -1;else{if (c[1] >= '0'&&c[1] <= '9')q[i].right = (c[0] - '0') * 10 + (c[1] - '0');elseq[i].right = c[0] - '0';vis[q[i].right] = 1;}}Tree Q = (Tree)malloc(sizeof(node));Q = NULL;if (m != 0){int root2 = 0;while (root2 < m){if (!vis[root2])break;root2++;}Q = CreateTree(Q, root2);}if (flag >= n){//如果不能成樹cout << "No." << endl;return 0;}else{//判斷是否同構(gòu) if (Judge(T, Q))cout << "Yes." << endl;elsecout << "No." << endl;}//system("pause"); return 0; }

補(bǔ)充說明

相信認(rèn)真的同學(xué)已經(jīng)發(fā)現(xiàn)代碼中有個 goto 語句來得莫名奇妙，搞不清所以然，下面容我來解釋一番。

每用 vis 標(biāo)記一個結(jié)點(diǎn)，計數(shù)器 flag 都加1。當(dāng) flag >= n 時，則意味著二叉樹實(shí)際的結(jié)點(diǎn)數(shù)多于輸入序列給出的結(jié)點(diǎn)數(shù)，因此無法建立二叉樹。

當(dāng)年這題的最后一個測試用例就是 flag >= n 導(dǎo)致無法建立第一棵樹，而我的代碼是先建立第一顆樹再讀取下一顆樹的信息，因此每次提交上去都是錯誤的結(jié)果。最后實(shí)在是沒招了，去找老師問了最后一個用例，才知道原來是測試用例的問題。（連樹都沒法建立，還談什么同構(gòu)啊）

當(dāng)年老師并沒有修改這個測試用例，因此我用了一個 goto 進(jìn)行了跳轉(zhuǎn)才 AC 了這題。看看下面的測試用例，再仔細(xì)比較讀取第一顆樹信息的代碼和讀取第二顆樹信息的代碼，你就會明白我說的是什么意思了。

3 A 1 2 B - - C 1 - 3 A 1 2 B - - C - -

也許現(xiàn)在老師已經(jīng)改過測試用例了，不會再出現(xiàn)當(dāng)年的問題，看懂上面的代碼，有針對性的做一些小的改動即可。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的二十、二叉树的同构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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