7-3 树的同构 (25 分) - C语言

7-3 树的同构

时间:2021年11月9日
作者:返祖猿
题目集:数据结构与算法题目集(中文)
题目:7-3 树的同构 (25 分)

1、前言

我居然解出一道树的题!!!

我很激动!!!

我准备趁热打铁把想法记录在这儿,如有雷同纯属偶然。

2、题目

7-3 树的同构 (25 分) - C语言

输入样例 1(对应图中的树)

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例 1

Yes

输入样例 2

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例 2

No

3、代码

#include<stdio.h>
typedef struct node{
	int id;
	char c;
	struct node *left;
	struct node *right;
} P;
int countChildren(P *pa);
int answer(P *pa, P *pb);
int main(){
	
	// 定义变量 
	P pa[10], pb[10];
	P *rootA, *rootB;
	int flagA[10] = {}, flagB[10] = {};
	int m, n, i;
	char temp;
	
	// 控制输入 1 
	scanf("%d", &n);
	for(i=0; i<n; i++){
		pa[i].id = i;
		// 左节点 
		scanf("\n%c %c ", &pa[i].c, &temp);
		if(isdigit(temp)){
			pa[i].left = &pa[temp-'0'];
			flagA[temp-'0'] = 1;
		} else {
			pa[i].left = NULL;
		}
		// 右节点 
		scanf("%c", &temp);
		if(isdigit(temp)){
			pa[i].right = &pa[temp-'0'];
			flagA[temp-'0'] = 1;
		} else {
			pa[i].right = NULL;
		}
	}
	
	// 控制输入 2 
	scanf("%d", &m);
	for(i=0; i<m; i++){
		pb[i].id = i;
		// 左节点 
		scanf("\n%c %c ", &pb[i].c, &temp);
		if(isdigit(temp)){
			pb[i].left = &pb[temp-'0'];
			flagB[temp-'0'] = 1;
		} else {
			pb[i].left = NULL;
		}
		// 右节点 
		scanf("%c", &temp);
		if(isdigit(temp)){
			pb[i].right = &pb[temp-'0'];
			flagB[temp-'0'] = 1;
		} else {
			pb[i].right = NULL;
		}
	}
	
	// ----------------------------------------------------------------
	// 排除显而易见的不同构树 
	if(n != m){
		printf("No");
		return 0;
	}
	if(n == 1){
		if(pa[0].c != pb[0].c){
			printf("No");
		} else {
			printf("Yes");
		}
		return 0;
	}
	if(n == 0){
		printf("Yes");
		return 0;
	}
	
	// 寻找两棵树的根节点 
	for(i=0; i<n; i++){
		if(flagA[i] == 0){
			rootA = &pa[i];
		}
		if(flagB[i] == 0){
			rootB = &pb[i];
		}
	}
	
	// test: 测试根节点是否正确 
//	printf("rootA: %d %c\n", rootA->id, rootA->c);
//	printf("rootB: %d %c\n", rootB->id, rootB->c);
	// true
	
	// 判断根节点是否相同 
	if(rootA->c != rootB->c){
		printf("No");
		return 0;
	}
	
	if(answer(rootA, rootB) == 0){
		printf("No");
	} else {
		printf("Yes");
	}
	return 0;
}

// 此方法判断节点有几个孩子 
int countChildren(P *pa){
	int count = 2;
	if(pa->left == NULL) count--;
	if(pa->right == NULL) count--;
	
	if(count == 2){
		return 2;
	} else if(count == 0){
		return 0;
	} else if(pa->left != NULL){
		return -1;
	} else if(pa->right != NULL){
		return 1;
	}
}

// 此方法递归判断两棵树的各节点的孩子是否相同 
int answer(P *pa, P *pb){
	
	int countA = countChildren(pa);
	int countB = countChildren(pb);
	
	P *tempA, *tempB;
	
	char pal, par, pbl, pbr;
	
	// 孩子数不同则不同构 
	if(abs(countA) != abs(countB)){
		return 0;
	}
	
	// 全是叶子节点的情况,因为送进来之前已经判断了两个节点相同,所以返回 1 
	if(countA == 0 && countB == 0){
		return 1;
	}
	
	// 都只有一个孩子的情况,这两个孩子保存的字符必须相同 
	if(countA != 2){
		
		if(countA>0){
			tempA = pa->right;
		} else {
			tempA = pa->left;
		}
		if(countB>0){
			tempB = pb->right;
		} else {
			tempB = pb->left;
		}
		
//		printf("\n%c %c\n", tempA->c, tempB->c);
		// note: return 的话程序就结束了,所以不会从这里进入两个孩子的情况 
		if(tempA->c == tempB->c){
			return answer(tempA, tempB);
		} else {
			return 0;
		}
	} 
	
	// 两个孩子的情况 
	pal = pa->left->c;
	par = pa->right->c;
	pbl = pb->left->c;
	pbr = pb->right->c;
//	printf("\n%c %c %c %c\n", pal, par, pbl, pbr);
	// note: 应该没有左右孩子相同的情况,吧…… 
	if((pal == pbl || pal == pbr)&&(par == pbl || par == pbr)){
		if(pal == pbl){
			return answer(pa->left, pb->left) && answer(pa->right, pb->right);
		} else {
			return answer(pa->left, pb->right) && answer(pa->right, pb->left);
		}
	} else {
		return 0;
	}
}

嗐,我自己都觉得这代码太长,真的有人看么 (←_←)

4、思考过程

① 寻找根节点

先不管其他的,读完输入后发现它的 根节点 都不按顺序给出来,着实劝退……

然后注意到根节点一定不会在每行输入的后两个数字中出现,于是用了一个很笨的方法寻找根节点:把输入的后两列数字记录,没有出现的那个数字就是根节点。

事实证明这个方法很好用~

② 实现检查同构

实现输入后开始思考如何实现判断两棵树同构的方法。

a. 寻找检查两个节点的两个孩子相同但顺序不同的方法

同构的最大特点就是两棵树同一节点的两个孩子相同,但顺序不同,然而一个节点有两个孩子,判断两个节点的两个孩子是否一样,还是稍微有点绕的。

  • 先在纸上写出了四个变量:pal, par, pbl, pbr,分别表示四个孩子;
  • 然后推出两个节点的两个孩子相同的判别式:(pal == pbl || pal == pbr) && (par == pbl || par == pbr);
  • 满足判别式的两个节点进入下一场递归:
    • if(pal == pbl) return answer(pa->left, pb->left) && answer(pa->right, pb->right);
    • else return answer(pa->left, pb->right) && answer(pa->right, pb->left);

此处解释一下我为什么要用递归呢,因为用 while 我不会写……咳,真的,有时会觉得递归比 while 还简单,这肯定不是我一个人的想法。

但是实现递归的时候就不会这么想了。

另外,也想过某个字节点的两个孩子里放的字符一样的情况,但从常识上考虑出题人应该不会如此疯狂……吧??姑且还是忽略了。

事实证明确实想太多,疯狂的只有我而已。

b. 排除显而易见的错误答案

当继续向下写的时候就要开始考虑答题了。

再读一遍题,我发现题目没有明说两棵树的节点不可能为 0,于是又仔细看了一遍,发现题目真的没有明说两棵树的节点不为 0,emmm,姑且写上了输出 “No”,提交一遍后发现专门有个测试点专门针对这种情况,而答案是 “Yes”,我竟无言以对。

当节点只有一个的时候,题目是很简单的。

如果两棵树的节点数不一样的话,这两棵树肯定是不同构的,为此还得定义 m 来控制第二课树的输入。需要注意的是,如果输入第二个节点数后立即判断、输出并 return,而不接收第二棵树的节点,pta 会因为没有完全接收它给出的数据而判错,这是另一道题的前车之鉴了。

没错,我连这种错都范过……

此外,多节点的情况下,根节点保存的字符不同也是显而易见的不同构,这同时解决了第一次进入递归的初始化问题。

c. 实现递归方法的主体内容

一时也想不到其他显而易见的错误了,于是回过头来继续做题。

因为是用递归写的代码,所以要好好规划一下这递归究竟如何使用:

  • 规定:进入递归的两个节点所保存的字符是相同的,即两个节点是同构的,孩子不论。
  • 二、递归判断的是两个节点的孩子是否保存着相同的字符,即判断孩子的同构。
  • 三、return 的是……emmm……一时间想不通这条咋叙述,所以 pass。

其实简单写下的规定还是有不明朗之处,但一时间也想不到许多,于是先把两个节点两个孩子的判断代码搬入递归方法中。方法名是 answer,因为一时间也想不到什么好名字了,甚至连写个 answer 都要百度咋拼

写着写着忽然想到,一个节点不一定有两个孩子,还有可能没有孩子,甚至另一个孩子是根本就不是节点(而是 NULL),一时间觉得写递归的难度飙升,劝退*2。

于是梳理了一下我的递归到底在写什么,记录下三条分支:

  • 每节点一个孩子;
  • 每个节点俩个孩子;
  • 节点无孩子;

废话文学实锤。

两个孩子的情况 pass。

当节点只有一个孩子时,首先要判断究竟是哪个孩子不是孩子(递归码字进行时),即另一个孩子是 NULL。

于是改了之前写的一个 判断两个节点保存的字符是否相同 的方法,来判断某个节点有几个孩子,方便起见,当节点的左孩子为 NULL 时返回 1,右孩子为 NULL 时返回 -1,是参考的横轴左负右正。结果后来还是用错了,纠错时长 + 20min。 方法名 countChildren。

countA = countChildren(pa),pb 同处理。

真正动手判断的时候甚至想过 char tempA = countA>0?pa->right->c:pa->right->c 这种扭曲写法,事实证明代码过于集成反而麻烦,于是改为 P tempA = countA>0?pa->right:pa->right,发现写到 right 的时候编译器没有及时提示,惊觉不靠谱,最终改成了简朴的 if 语句。

其实加上 ( ) () () 就没问题了。

d. 完善递归方法及主方法

当写完只有一个孩子的情况,发现还有个 “节点无孩子” 在等着我,简直累感不爱。

不过代码都已经完成到这一步了,难道还要退缩吗?No.

写只有一个孩子的情况时就想到,如果两个节点的孩子数不同,两节点同样不同构,于是加上了这条判断。

这里还有个小失误,因为 countChildren 返回 1 也返回 -1,得给它套个 abs 才能放心比较,纠错时常 + 20min。

节点无孩子倒是简单,因为规定了进入递归的两节点是同构的,直接返回 1。

至此,递归方法结束。

③ 最终梳理程序

检查一遍主方法后,主方法也结束了。

因为写代码的时候比较细心,六个监测点里只错了一个,还是因为空树返回 Yes 或 No 而错的,说实话有点小开心。这里要是错一大片简直崩溃。

倒是测试用例的时候纠错好长时间,无语无语,冷静冷静,兜住兜住━━( ̄ー ̄*|||━━

5、后记

这不是第一次做出 25 分的题,但是第一次做对树,很有成就感。

至今连根据前序遍历和中序遍历推导树的结构都做不到。

各位看官要是有感而发,欢迎评论区分享。

没有的话就算了,毕竟我也不看这种又臭又长的文(doge

千言万语无墨可落,不必关注,有缘再见。

黑历史 + 1

上一篇:C语言_指针变量的赋值与运算,很详细


下一篇:c语言指针自学