03-树1-树的同构-编程题

解题代码

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 10
typedef struct Node stynode;
struct Node {
	char data;
	int left;
	int right;
}node1[MaxSize], node2[MaxSize];
int Read(stynode node[]);
int Judge(int r1, int r2);
int main()
{
	int  r1, r2;
	r1 = Read(node1);
	r2 = Read(node2);
	if (Judge(r1, r2)) printf("Yes");
	else printf("No");
	return 0;
}
int Read(stynode node[])
{
	int n1, i, r1 = -1;
	char tl, tr, temp;
	scanf("%d", &n1);
	if (!n1) return r1;
	int* a1 = (int*)malloc(n1 * sizeof(int));
	for (i = 0; i < n1; i++) {
		a1[i] = 0;
	}
	for (i = 0; i < n1; i++) {
		temp = getchar();
		scanf("%c %c %c", &node[i].data, &tl, &tr);
		//printf("node1[%d].data=%c\n", i, node[i].data);
		if (tl >= '0' && tl <= '9') {
			node[i].left = tl - '0';
			a1[node[i].left] = 1;
		}
		else node[i].left = -1;
		if (tr >= '0' && tr <= '9') {
			node[i].right = tr - '0';
			a1[node[i].right] = 1;
		}
		else node[i].right = -1;
	}
	for (i = 0; i < n1; i++) {
		if (!a1[i]) break;
	}
	if (i != n1) r1 = i;
	return r1;
}
int Judge(int r1, int r2)
{
	//printf("%d %d\n", r1, r2);
	int A, B;

	if ((r1 == -1) && (r2 == -1)) return 1;

	if (((r1 == -1) && (r2 != -1)) || ((r1 != -1) && (r2 == -1))) 	return 0;

	if (node1[r1].data != node2[r2].data) {
		//printf("node1[%d].data=%c,node2[%d].data=%c", r1, node1[r1].data, r2, node2[r2].data);
		return 0;
	}

	if ((node1[r1].left == -1) && (node2[r2].left == -1)) return Judge(node1[r1].right, node2[r2].right);

	if (((node1[r1].left != -1) && (node2[r2].left != -1)) && (node1[node1[r1].left].data == node2[node2[r2].left].data)) return ((A = Judge(node1[r1].left, node2[r2].left)) && (B = Judge(node1[r1].right, node2[r2].right)));

	else return ((A = Judge(node1[r1].left, node2[r2].right)) && (B = Judge(node1[r1].right, node2[r2].left)));
}

测试结果

问题整理

1.注意全局变量的使用！不要在不该改动的地方随意改动。
2注意分类讨论的种种情况。