欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基础实验4-2.1-树的同构-编程题

程序员文章站 2022-03-13 16:01:54
...

基础实验4-2.1-树的同构-编程题

解题代码

#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));
}

测试结果

基础实验4-2.1-树的同构-编程题

问题整理

1.int CreatSTree(pST T, int N) 建树时,注意两点:
	-tleft,tright的数据类型;
	-N==0时的边界条件判断;