題目
給定兩棵樹(shù)T1和T2。如果T1可以通過(guò)若干次左右孩子互換就變成T2，則我們稱(chēng)兩棵樹(shù)是“同構(gòu)”的。例如圖1給出的兩棵樹(shù)就是同構(gòu)的，因?yàn)槲覀儼哑渲幸豢脴?shù)的結(jié)點(diǎn)A、B、G的左右孩子互換后，就得到另外一棵樹(shù)。而圖2就不是同構(gòu)的。
輸入格式:
輸入給出2棵二叉樹(shù)樹(shù)的信息。對(duì)于每棵樹(shù)，首先在一行中給出一個(gè)非負(fù)整數(shù)N (≤10)，即該樹(shù)的結(jié)點(diǎn)數(shù)（此時(shí)假設(shè)結(jié)點(diǎn)從0到N?1編號(hào)）；隨后N行，第i行對(duì)應(yīng)編號(hào)第i個(gè)結(jié)點(diǎn)，給出該結(jié)點(diǎn)中存儲(chǔ)的1個(gè)英文大寫(xiě)字母、其左孩子結(jié)點(diǎn)的編號(hào)、右孩子結(jié)點(diǎn)的編號(hào)。如果孩子結(jié)點(diǎn)為空，則在相應(yīng)位置上給出“-”。給出的數(shù)據(jù)間用一個(gè)空格分隔。注意：題目保證每個(gè)結(jié)點(diǎn)中存儲(chǔ)的字母是不同的。
輸出格式:
如果兩棵樹(shù)是同構(gòu)的，輸出“Yes”，否則輸出“No”。
輸入樣例1（對(duì)應(yīng)圖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（對(duì)應(yīng)圖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
題解
直觀上感覺(jué)用數(shù)組做比較簡(jiǎn)單，所以以下是用數(shù)組完成的代碼.
關(guān)鍵是找出根節(jié)點(diǎn)與判斷是否同構(gòu)。這個(gè)函數(shù)比較復(fù)雜也很暈，需要考慮周全
#include<iostream>
using namespace std;
typedef char ElementType;
typedef struct TreeNode Tree;
//結(jié)構(gòu)體
struct TreeNode {
ElementType data;
int left;
int right;
}t1[101],t2[101];
//建樹(shù)
int Build(Tree t[])
{
bool a[101] = { false };
int n;
cin >> n;
char data, left, right;
for (int i = 0; i < n; i++)
{
cin >> data >> left >> right;
t[i].data = data;
//判斷左右節(jié)點(diǎn)是否空
if (left == '-')
t[i].left = -1;
else {
t[i].left = left-'0';
a[(int)left - 48] = true;
}
if (right == '-')
t[i].right = -1;
else {
t[i].right = (int)right-48;
a[(int)right - 48] = true;
}
}
//判斷是不是根節(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有雙親結(jié)點(diǎn)
for (int i = 0; i < n; i++)
{
//cout << t[i].data <<" "<< t[i].left <<" "<< t[i].right <<" "<< a[i] << endl;;
if (!a[i])
return i;
}
return -1;
}
bool Compare(int r1,int r2)
{
if (r1 == -1 && r2 == -1)
return true;
else if ((r1 == -1 && r2 != -1) || (r2 == -1 && r1 != -1))
return false;
else if (t1[r1].data != t2[r2].data)
return false;
else if (t1[r1].left == -1 && t2[r2].left == -1)
return Compare(t1[r1].right, t2[r2].right);
else if ((t1[r1].left != -1 && t2[r2].left != -1) && (t1[t1[r1].left].data == t2[t2[r2].left].data))
return Compare(t1[r1].left, t2[r2].left) && Compare(t1[r1].right, t2[r2].right);
else
return Compare(t1[r1].left, t2[r2].right) && Compare(t1[r1].right, t2[r2].left);
}
int main()
{
int root1 = Build(t1);
int root2 = Build(t2);
cout << root1 << " " << root2 << " ";
bool flag = Compare(root1, root2);
if (flag)
cout << "Yes" << endl;
else
cout << "No" << endl;
system("pause");
return 0;
}
