带你用Java方法轻松实现树的同构

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

树的同构

举例

在这里插入图片描述

树的构造

树可以由数组或链表来构造：

举例：上图左上角的树通过数组可表示为

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

该方式浪费了部分空间，但适合表示完全二叉树

链表方式则比较直观

除上述两种方式外，还可以采用“类数组”的方式

 public static class Node{ String data; int left; int right; }

举例：上图左上角的树可表示为

数组索引	data	left	right
0	A	1	2
1	B	3	4
2	C	6	-
3	D	-	-
4	E	5	-
5	F	-	-
6	G	7	-
7	H	-	-

本文的树结构使用了第三种方式

终端输入：

 A,1,2 B,3,- C,-,- D,-,- A,2,1 B,3,- C,-,- D,-,-

 public class TongGou { private Scanner scanner; public TongGou(){ scanner = new Scanner(System.in); } //树结构 public static class Node{ String data; int left; int right; } /** * 创建树 * @param nodes * @return */ public int createTree(Node[] nodes){ int N = nodes.length; int root = -1; int[] check = new int[N]; Arrays.fill(check,0);  //初始化为0 for (int i=0;i0) { check[left] = 1; } if(right>0){ check[right] = 1; } } } for(int i=0;i