基础实验4-2.1-树的同构-编程题
程序员文章站
2022-03-13 16:01:54
...
解题代码
#include<stdio.h>
#include<stdlib.h>
typedef enum{false,true} bool;
typedef struct STNode* pST;
struct STNode {
char data;
int left;
int right;
};
int CreatSTree(pST T, int N);
bool Isomorphism(pST T1, pST T2, int R1, int R2);
int main()
{
int N1;//n of stree1
int R1 = -1, R2 = -1;
scanf("%d", &N1);
pST T1 = (pST)malloc(N1 * sizeof(struct STNode));
R1 = CreatSTree(T1, N1);
int N2;//n of stree2
scanf("%d", &N2);
pST T2 = (pST)malloc(N2 * sizeof(struct STNode));
R2 = CreatSTree(T2, N2);
if (N1 != N2) printf("No");
else if (Isomorphism(T1, T2, R1, R2)) printf("Yes");
else printf("No");
return 0;
}
int CreatSTree(pST T, int N) {
if (!N) return -1;
int i;
char tleft, tright;
int* check = (int *)malloc(N * sizeof(int));
for (i = 0; i < N; i++) check[i] = 0;
for (i = 0; i < N; i++) {
scanf("\n%c %c %c", &T[i].data, &tleft, &tright);
if (tleft == '-') T[i].left = -1;
else {
T[i].left = tleft - '0';
check[T[i].left] = 1;
}
if (tright == '-') T[i].right = -1;
else {
T[i].right = tright - '0';
check[T[i].right] = 1;
}
}
for (i = 0; i < N; i++) if (!check[i]) return i;
}
bool Isomorphism(pST T1, pST T2, int R1, int R2) {
if (R1 == -1 && R2 == -1) return true;
if (R1 != -1 && R2 == -1 || R1 == -1 && R2 != -1) return false;
if (T1[R1].data != T2[R2].data) return false;
if (T1[R1].left == -1 && T2[R2].left == -1 || T1[R1].left != -1 && T2[R2].left != -1 && T1[T1[R1].left].data == T2[T2[R2].left].data) return Isomorphism(T1, T2, T1[R1].right, T2[R2].right);
else return (Isomorphism(T1, T2, T1[R1].left, T2[R2].right) && Isomorphism(T1, T2, T1[R1].right, T2[R2].left));
}
测试结果
问题整理
1.int CreatSTree(pST T, int N) 建树时,注意两点:
-tleft,tright的数据类型;
-N==0时的边界条件判断;
上一篇: 打印沙漏