编写c语言程序判断树是否同构?其中同构是指给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则称两棵树是“同构”的,输出True,否则输出False。 输入:第一行N,表示树的结点数; 第二行开始:结点数据 左孩子编号 右孩子编号,如果无孩子结点记为“-1”。 输入样例: 8 A 1 2 B 3 4 C 5 -1 D -1 -1 E 6 -1 G 7 -1 F -1 -1 H -1 -1 8 G -1 4 B 7 6 F -1 -1 A 5 1 H -1 -1 C 0 -1 D -1 -1 E 2 -1 输出样例:True
时间: 2023-06-11 16:05:08 浏览: 56
对于这个问题,可以考虑递归判断两个树是否同构。具体而言,需要判断根节点是否相同,左子树是否同构,右子树是否同构。同时,需要注意左右子树的位置是可以互换的,因此还需要判断左子树是否同构右子树。
以下是代码实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 10010
int n;
char data1[MAXN], data2[MAXN];
int left1[MAXN], left2[MAXN], right1[MAXN], right2[MAXN];
/* 等价数组,表示以root1和root2为根的两棵子树是否同构 */
int eqv[MAXN][MAXN];
int build(char *data, int *left, int *right) {
int root = -1;
if (*data != '-') {
root = *data - 'A';
if (left[root] == -1 && right[root] == -1) {
left[root] = right[root] = -1;
} else {
left[root] = build(data + 2, left, right);
right[root] = build(strchr(data + 2, ' ') + 1, left, right);
if (left[root] > right[root]) {
int temp = left[root];
left[root] = right[root];
right[root] = temp;
}
}
}
return root;
}
/* 判断以root1和root2为根的两个子树是否同构 */
int isomorphic(int root1, int root2) {
if (root1 == -1 && root2 == -1) {
return 1;
} else if (root1 == -1 || root2 == -1) {
return 0;
}
if (data1[root1] != data2[root2]) {
return 0;
}
if (eqv[root1][root2]) {
/* 已经计算过了,直接返回结果 */
return eqv[root1][root2] - 1;
}
/* 左右子树位置可以互换 */
if ((isomorphic(left1[root1], left2[root2]) && isomorphic(right1[root1], right2[root2])) ||
(isomorphic(left1[root1], right2[root2]) && isomorphic(right1[root1], left2[root2]))) {
eqv[root1][root2] = 2; /* 记录结果 */
return 1;
} else {
eqv[root1][root2] = 1; /* 记录结果 */
return 0;
}
}
int main() {
scanf("%d", &n);
memset(left1, -1, sizeof(left1));
memset(left2, -1, sizeof(left2));
memset(right1, -1, sizeof(right1));
memset(right2, -1, sizeof(right2));
for (int i = 0; i < n; i++) {
char c, lc, rc;
scanf(" %c %c %c", &c, &lc, &rc);
data1[i] = data2[i] = c;
left1[i] = left2[i] = lc == '-' ? -1 : lc - '0';
right1[i] = right2[i] = rc == '-' ? -1 : rc - '0';
}
/* 构建两棵树 */
build(data1, left1, right1);
build(data2, left2, right2);
/* 判断是否同构 */
if (isomorphic(0, 0)) {
printf("True\n");
} else {
printf("False\n");
}
return 0;
}