03-树1 树的同构(浙大数据结构PTA习题）

03-树1 树的同构分数 25 作者陈越单位浙江大学

给定两棵树 T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。


图1

图2

现给定两棵树，请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树的信息。对于每棵树，首先在一行中给出一个非负整数 n (≤10)，即该树的结点数（此时假设结点从 0 到 n−1 编号）；随后 n 行，第 i 行对应编号第 i 个结点，给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出 “-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的，输出“Yes”，否则输出“No”。

输入样例1（对应图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（对应图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

代码长度限制：16 KB 时间限制：400 ms 内存限制：64 MB

题目解析：

第一个关键点：如何找出树的根结点

第二个关键点：知道树的根结点后如何构建树

采用递归的思路，如果根结点的左子树不为空，则递归构建，否则为NULL；如果根结点的右子树不为空，则递归构建，否则为NULL；

第三个关键点：如何判断两棵树是否同构

采用递归的思路：（1）两棵树的根结点都为NULL，则两棵树同构；（2）两个根结点相同的前提下，（树1的左子树与树2的左子树同构并且树1的右子树与树2的右子树同构）或者（树1的左子树与树2的右子树同构并且树1的右子树与树2的左子树同构），则两棵树同构；

代码展示：

# include<stdio.h>
# include<stdbool.h>
# include<stdlib.h>

typedef char ElementType;

typedef struct TreeNode* Tree;
struct TreeNode{
	ElementType info,left,right;
	Tree Left;
	Tree Right;
};

bool IsSame(Tree Tree1, Tree Tree2);
Tree Create();
Tree InitialTree(Tree Array[],int N);
Tree CreateTree(Tree Array[],Tree Root);


int main(){
	// 构建两棵树 
	Tree tree1 = Create();
	Tree tree2 = Create();
	// 判读这两棵树是否同构 
	if(IsSame(tree1,tree2))printf("Yes");
	else printf("No");
	return 0; 
}

// 根据输入创建一棵树
Tree Create(){
	int N;
	scanf("%d",&N);
	getchar();
	// 易错：如果一来就是空树，那么直接返回空树，否则后面会发生段错误
	if(N==0)return NULL; 
	Tree Array[N];
	// 将信息存入指针数组中并获得树的根结点
	Tree Root = InitialTree(Array,N);
	// 通过树的根结点来建立树 
	Tree tree = CreateTree(Array,Root);
	return tree; 
} 

// 将结点信息存入指针数组中，并返回树的根结点 
Tree InitialTree(Tree Array[],int N){
	// Check数组用来标记结点是否作为了子节点 
	int i,Check[N];
	for(i=0;i<N;i++)Check[i] = 1;
	// 读入结点信息，并判读每个结点是否作为了子节点 
	for(i=0;i<N;i++){
		Tree node = (Tree)malloc(sizeof(struct TreeNode));
		node->info = getchar();
		getchar();
		node->left = getchar();
		if(node->left!='-')Check[node->left-'0'] = 0;
		getchar();
		node->right = getchar();
		if(node->right!='-')Check[node->right-'0'] = 0;
		getchar();
		node->Left = node->Right = NULL;
		Array[i] = node;
	}
	for(i=0;i<N;i++){
		if(Check[i]==1)break;
	}
	return Array[i];
}

// 根据指针数组递归构建一棵树
Tree CreateTree(Tree Array[],Tree Root){
	int i,count;
	// 递归构建左子树 
	if(Root->left == '-'){
		Root->Left = NULL;
	}else{
		Root->Left = CreateTree(Array,Array[Root->left-'0']);
	}
	// 递归构建右子树
	if(Root->right == '-'){
		Root->Right = NULL;
	}else{
		Root->Right = CreateTree(Array,Array[Root->right-'0']);
	}
	return Root;
} 

// 递归判读两棵树是否同构
bool IsSame(Tree Tree1, Tree Tree2){
	// 根结点都为空，则视为同构
	if(Tree1==NULL && Tree2==NULL)return true;
	// 根结点一个为空，一个不为空，则不同构
	if(Tree1==NULL && Tree2 || Tree1 && Tree2==NULL)return false;
	// 根结点都为不为空，但不相同，则不同构
	if(Tree1->info != Tree2->info)return false;
	// Tree1的左子树与Tree2的左子树同构 并且 Tree1的右子树与Tree2的右子树同构 
	if(IsSame(Tree1->Left,Tree2->Left)&&IsSame(Tree1->Right,Tree2->Right))return true;
	// Tree1的左子树与Tree2的右子树同构 并且 Tree1的右子树与Tree2的左子树同构 
	if(IsSame(Tree1->Left,Tree2->Right)&&IsSame(Tree1->Right,Tree2->Left))return true; 
}