专题：树的同构

Mycode:

#include<cstdio>
#include<cstdlib>
using namespace std;

/*判断树的同构:给定两棵树T1和T2，如果T1可以通过若干次左右孩子互换
  变成T2，则称这两棵树是同构的。
  结构数组表示二叉树：静态链表
*/
#define MaxTree 15
#define ElementType char
#define Tree int
#define Null -1
typedef struct TreeNode Tr;

struct TreeNode{
	ElementType Element;
	Tree Left;	//左子树的编号
	Tree Right;	//右子树的编号
}T1[MaxTree], T2[MaxTree];	//T1,T2为结构数组表示的二叉树

Tree BuildTree(Tr T[]){
	//check数组用来标记每个结点的左右子树编号，
	//最后遍历没有被标记的就是根结点
	Tree Root = Null, check[MaxTree];
	Tree N;
	ElementType cl, cr;
	scanf("%d", &N);
	if (N){
		for(int i = 0; i < N; i++) check[i] = 0;
		for(int i = 0; i < N; i++){
			//输入需要注意防止scanf接收了回车或者空格等字符
			scanf(" %c %c %c", &T[i].Element, &cl, &cr);
			if (cl != '-'){
				T[i].Left = cl - '0';
				check[T[i].Left] = 1;
			}
			else T[i].Left = Null;
			if (cr != '-'){
				T[i].Right = cr - '0';
				check[T[i].Right] = 1;
			}
			else T[i].Right = Null;
		}
		for(int i = 0; i < N; i++)
			if (!check[i]){
				Root = i;
				break;
			}
	}
	return Root;
}

bool Isomorphic(Tree R1, Tree R2){
	if (R1 == Null && R2 == Null)	//两棵树均为空树
		return true;
	if (((R1 == Null) && (R2 != Null)) || ((R1 != Null) && (R2 == Null)))
		//两棵树一颗为空树，另一颗非空
		return false;
	if (T1[R1].Element != T2[R2].Element)
		//根结点不同
		return false;
	if ((T1[R1].Left == Null) && (T2[R2].Left == Null))
		//两颗树都没有左子树,递归判断右子树是否同构
		return Isomorphic(T1[R1].Right, T2[R2].Right);
	if (((T1[R1].Left != Null)&&(T2[R2].Left != Null)) && ((T1[T1[R1].Left].Element) == (T2[T2[R2].Left].Element)))
		//如果两颗树的左子树均不为空且左子树的根相同,则不需要交换左右子树
		//继续判断左子树右子树是否同构即可
		return (Isomorphic(T1[R1].Left, T2[R2].Left) && Isomorphic(T1[R1].Right, T2[R2].Right));
	else	//需要交换左右子树
		return (Isomorphic(T1[R1].Left, T2[R2].Right) && Isomorphic(T1[R1].Right, T2[R2].Left));
}

int main(){
	Tree R1, R2;	//R1,R2为T1,T2的根结点
	R1 = BuildTree(T1);
	R2 = BuildTree(T2);
	if (Isomorphic(R1, R2)) printf("Yes\n");
	else printf("No\n");
}