7-34 树的同构 (25分)（思路+代码 递归实现）

思路:这道题让判断两个树是否同构，那么我们首先要建立出来这两颗树，然后用一个数组pre来存储各节点之间的关系，然后找出这两颗树的根节点。做到这里，基本就已经完成了，接下来就是判断。这里用到了递归判断，判断过程大致如下（具体可结合代码）：
1.先判断两颗树是否为空，如果都是空树，肯定一样，如果一个为空一个不为空就肯定不一样。
2.判断根节点的值是否一样，如果根节点值就不一样那肯定不一样
3.判断左子树，如果两个左子树为空就递归判断右子树。如果两个左子树都不为空且值一样，那么就递归判断左子树的左子树和右子树。 （这句话可能看起来有点复杂，最好画棵树你细品）
4.最后交叉判断，第一颗左子树和第二颗右子树。第一颗右子树和第二课左子树。
代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node
{
	char data;
	int left,right;
}t1[12],t2[12];
int read(node t[])
{
	int n,root=-1,pre[12];
	memset(pre,0,sizeof pre);
	char l,r;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>t[i].data>>l>>r;
		if(l!='-')
		{
			t[i].left=l-'0';
			pre[t[i].left]=1;
		}
		else	t[i].left=-1;
		if(r!='-')
		{
			t[i].right=r-'0';
			pre[t[i].right]=1;
		}
		else	t[i].right=-1;
	}
	for(int i=0;i<n;i++)
		if(!pre[i])		return i;
	return root;
}
int isSame(int root1,int root2)
{
	if((root1==-1)&&(root2==-1))	return 1;
	if((root1==-1)&&(root2!=-1)||(root1!=-1&&root2==-1))	return 0;
	if((t1[root1].data)!=(t2[root2].data))	return 0;
	if((t1[root1].left==-1)&&(t2[root2].left==-1))	
		return isSame(t1[root1].right,t2[root2].right);
	if((t1[root1].left!=-1)&&(t2[root2].left!=-1)&&(t1[t1[root1].left].data==t2[t2[root2].left].data))
		return (isSame(t1[root1].left,t2[root2].left)&&isSame(t1[root1].right,t2[root2].right));
	return (isSame(t1[root1].left,t2[root2].right)&&isSame(t1[root1].right,t2[root2].left)); 
}
int main()
{
	int root1,root2;
	root1=read(t1);
	root2=read(t2);
	if(isSame(root1,root2))	cout<<"Yes"<<endl;
	else	cout<<"No"<<endl;
}