7-3-树的同构-编程题

解题代码

#include<stdio.h>
#include<stdlib.h>
typedef enum{false,true} bool;
typedef struct TNode* Tree;
struct TNode {
	char Data;
	int Left;
	int Right;
};
Tree newTree(int N, int* r);
bool Judge(Tree T1, Tree T2, int r1, int r2);
int main()
{
	int N1,N2;//number of TNode
	int r1=-1, r2=-1;//root of Tree
	scanf("%d", &N1);
	Tree T1 = newTree(N1,&r1);
	scanf("%d", &N2);
	Tree T2 = newTree(N2,&r2);
	if (Judge(T1, T2, r1, r2)) printf("Yes");
	else printf("No");
	return 0;
}
Tree newTree(int N,int* r) {
	if (!N) return NULL;
	Tree T = (Tree)malloc(10 * sizeof(struct TNode));
	char tleft, tright, tdata;
	int i;
	int check[10] = { 0 };
	for (i = 0; i < N; i++) {
		getchar();
		scanf("%c %c %c", &tdata, &tleft, &tright);
		T[i].Data = tdata;
		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]) break;
	}
	*r = i;
	return T;
}
bool Judge(Tree T1, Tree 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) return Judge(T1, T2, T1[r1].Right, T2[r2].Right);
	else if(T1[r1].Left!=-1&&T2[r2].Left!=-1&&T1[T1[r1].Left].Data==T2[T2[r2].Left].Data) return Judge(T1, T2, T1[r1].Right, T2[r2].Right);
	else return Judge(T1, T2, T1[r1].Left, T2[r2].Right) && Judge(T1, T2, T1[r1].Right, T2[r2].Left);
}

测试结果

问题整理

1.关于迭代中的return：只要迭代过程中，迭代函数出现在了return后边，那所有的if出口都要跟上return以便使迭代函数在任何情况下都有明确的赋值。