树的同构（java实现）

7-3 树的同构（25 分）

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

                                                                                        图1

                                                                                        图2

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

输入格式:

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数$N$ ($\le 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

思路：

1、只在主函数中定义scanner，然后作为参数传递给读入函数。不要在读入函数中定义，因为要读两次，定义两个scanner的话，输入是一下子输进来，会出错。

2、因为这个题目是N在10以内，如果再大一点，怎样判断‘-’是字符呢还是数字45呢？就用String来接受，然后判断str.equals("-")就可以了。一定注意String不要用==。

3、用递归来判断树是否同构，注意分类。

4、怎样在java中定义全局变量呢，就是把他作为Main类的public的数据域，定义在主函数外。

5、用数组来存储对象时，你new一个数组是不会对对象进行初始化的。对每一个元素必须有new对象的操作。

 import java.util.Scanner;  public class Main { 	 	public static int n1=-1; 	 	 	public static void main(String[] args) { 		// TODO Auto-generated method stub 		Scanner in = new Scanner(System.in); 		Jiedian [] A = read(in); 		int root1=n1;  		 		Jiedian [] B = read(in); 		int root2=n1; 		boolean bool = istg(root1,A,root2,B); 		if(bool) 			System.out.println("Yes"); 		else 			System.out.println("No");  	}  	private static void print(Jiedian[] a) { 		// TODO Auto-generated method stub 		for(Jiedian jd:a) { 			System.out.println(jd.element+"  "+jd.left+"  "+jd.right); 		} 	}  	private static boolean istg(int root1, Jiedian[] a, int root2, Jiedian[] b) { 		// TODO Auto-generated method stub 		if(root1==-1&&root2==-1) 			return true; 		else if((root1==-1&&root2!=-1)||(root1!=-1&&root2==-1)) 			return false; 		else if (a[root1].element!=b[root2].element) 			return false; 		else if(istg(a[root1].left,a,b[root2].left,b)&&istg(a[root1].right,a,b[root2].right,b)) 			return true; 		else if(istg(a[root1].left,a,b[root2].right,b)&&istg(a[root1].right,a,b[root2].left,b)) 			return true; 		 		return false; 	}  	private static Jiedian [] read(Scanner in) { 		// TODO Auto-generated method stub //		Scanner in = new Scanner (System.in); 		 		int n = in.nextInt(); 		 		int check [] = new int[n]; 		for(int i = 0;i<n;i++) { 			check[i]=-2; 		} 		 		Jiedian [] jd = new Jiedian[n]; 		 		 		for(int i=0; i<n ; i++) { //			System.out.println(i); 			jd[i]=new Jiedian(); 			 			 			String str = in.next(); //			System.out.println(str); 			 			 			jd[i].element=str.charAt(0);  			 			str=in.next(); 			if(!str.equals("-")) 			{ 				int temp; 				temp=Integer.parseInt(str); 				jd[i].left=temp; 				check[temp]=temp;; 				 			} 			 			else 				jd[i].left=-1; 			 			str = in.next();  			if(!str.equals("-")) 			{ 				int temp; 				temp=Integer.parseInt(str); 				jd[i].right=temp; 				check[temp]=temp; 				 			} 				 			else 				jd[i].right=-1; 	 		} 		 寻找根节/ 		for(int i=0;i<n;i++) 		{ 			if(check[i]==-2) 				{ 					n1=i; 					break; 				} 		} 		 		// 		 		return jd; 	} 	 }  class Jiedian{ 	public char element ; 	public int left ; 	public int right; 	 }