PTA 7-1 树的同构(25 分)

时间:2021-04-21 12:27:04

7-1 树的同构(25 分)

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。

PTA 7-1 树的同构(25 分)

图1

PTA 7-1 树的同构(25 分)

图2

现给定两棵树,请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数N (10),即该树的结点数(此时假设结点从0到N1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的,输出“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

思路:

    说实话这题我根本就没有和树扯上太大关系。。。。。
     这题只需要抓住一个要点——若两树同构,则他们的每一个节点相同,且节点的儿子也相同(不分左右)
     只需要根据这一点,再对数据做些处理即可。

代码:

#include 
   
   
   

using namespace std;
typedef struct Node
{
char ch; // 节点所储存的字母
char left;// left - '0' 即为此节点左儿子在数组中的下标
char right;
};
Node tree[12][2];
int n1,n2;
void Init(int id)
{
int n;
scanf("%d",&n);
if(id == 0)
n1 = n;
else n2 = n;
char a,b,c,d,e,f;
getchar();
for(int i = 0; i < n; ++i)
{
scanf("%c%c%c%c%c%c",&a,&b,&c,&d,&e,&f);
tree[i][id].ch = a;
if(e == '-'&& f != '-') swap(e,f);//确保若只有一个儿子,则一定是左儿子
tree[i][id].left = c;
tree[i][id].right = e;
}
}
bool solve()
{
int ok = 1;
if( n1 != n2 ) return false;
for(int i = 0; i < n1; ++i)
{
int j ;
char l2, r2;
char c1 = tree[i][0].ch, l1 = tree[i][0].left, r1 = tree[i][0].right;
for(j = 0; j < n2; ++j)//在另个一树中找到ch相同的节点,并对他们的儿子是否相同进行判断
{
if(c1 == tree[j][1].ch)
{
l2 = tree[j][1].left;
r2 = tree[j][1].right;
break;
}
}
if( j == n2) {ok = 0; break;}//第一个树中含有第二个树不存在的节点,可判断不同构
if(r1 == '-' && r2 == '-')// 注意当节点中的left 或者 right 为‘-’时要进行特殊处理
{
if(l1 == '-' && l2 == '-')
continue;
else if(tree[l1 - '0'][0].ch == tree[l2 - '0'][1].ch)
continue;
else {ok = 0; break;}
}
else if(((tree[l1 - '0'][0].ch == tree[l2 - '0'][1].ch)&&(tree[r1 - '0'][0].ch == tree[r2 - '0'][1].ch))||
((tree[l1 - '0'][0].ch == tree[r2 - '0'][1].ch)&&(tree[r1 - '0'][0].ch == tree[l2 - '0'][1].ch)))
continue ;
else {ok = 0; break;}

}
if(ok) return true;
else return false;
}
int main()
{

Init(0);
Init(1);
if(solve()) printf("Yes");
else printf("No");
return 0;
}