Java如何实现树的同构?
作者:dztom 时间:2023-11-28 09:55:19
树的同构
备忘!
定义:给定两棵树r1、r2,如果r1可以通过若干次的左子树和右子树互换,使之与r2完全相同,这说明两者同构。
举例
树的构造
树可以由数组或链表来构造:
举例:上图左上角的树通过数组可表示为
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;i<N;i++){
//输入格式 data,left,right
String next = scanner.next();
String[] inputList = next!=null?next.split(","):null;
if(inputList!=null&&inputList.length==3){
nodes[i] = new Node();
int left = "-".equals(inputList[1])?-1:Integer.parseInt(inputList[1]);
int right = "-".equals(inputList[2])?-1:Integer.parseInt(inputList[2]);
nodes[i].data = inputList[0];
nodes[i].left = left;
nodes[i].right = right;
if(left>0) {
check[left] = 1;
}
if(right>0){
check[right] = 1;
}
}
}
for(int i=0;i<check.length;i++){
if(check[i]==0&&nodes[i].data!=null){
root = i;
break;
}
}
return root;
}
/**
* 判断同构
* @param r1
* @param r2
* @return
*/
public boolean isomorphic(int r1,int r2,Node[] t1,Node[] t2){
//须注意不要漏掉逻辑!
//两个根节点均为null,必同构
if ((r1 == -1) && (r2 == -1)) {
return true;
}
//一个非空 另一个空,必不同构
if(((r1==-1)&&(r2!=-1))||((r1!=-1)&&(r2==-1))){
return false;
}
//两个节点非空 但值不同,必不同构
if(!t1[r1].data.equals(t2[r2].data)){
return false;
}
//两根节点的左孩子为空条件下,则须判断两根节点的右子树是否同构
if(t1[r1].left==-1&&t2[r2].left==-1){
return isomorphic(t1[r1].right,t2[r2].right,t1,t2);
}
//两根节点的左孩子不为空且左孩子的值也相同,须判断两根节点的左子树是否同构以及两根节点的右子树是否同构
//如果左右子树均同构,则整棵树同构
if((t1[r1].left!=-1&&t2[r2].left!=-1)&&(t1[t1[r1].left].data.equals(t2[t2[r2].left].data))){
return isomorphic(t1[r1].left,t2[r2].left,t1,t2)&&isomorphic(t1[r1].right,t2[r2].right,t1,t2);
}else{
//分两种情况解释:
//1、两根节点的左孩子不为空,但左孩子的值不同
//例如:t1[r1.left].data!=t2[r2.left].data。但有t1[r1.left].data==t2[r2.right].data、t1[r1.right].data==t2[r2.left].data
//即有可能r1的左子树与r2的右子树同构、r1的右子树与r2的左子树同构
//故须判断r1的左子树是否与r2的右子树同构,以及r1的右子树是否与r2的左子树同构
//2、两根节点的左孩子一个为空,一个不为空
//例如:r1.left==-1、r2.left!=-1,如果r2.right==-1,显然r1的左子树与r2的右子树同构,此时则有可能r1的右子树与r2的左子树同构
//故须判断r1的左子树是否与r2的右子树同构,以及r1的右子树是否与r2的左子树同构
return isomorphic(t1[r1].left,t2[r2].right,t1,t2)&&isomorphic(t1[r1].right,t2[r2].left,t1,t2);
}
}
public static void main(String[] args) {
TongGou tongGou = new TongGou();
Node[] nodes = new Node[4];
Node[] nodes1 = new Node[4];
int tree1 = tongGou.createTree(nodes);
System.out.println();
int tree2 = tongGou.createTree(nodes1);
boolean isomorphic = tongGou.isomorphic(tree1, tree2, nodes, nodes1);
System.out.println(isomorphic);
}
}
来源:https://blog.csdn.net/dztom/article/details/117910267
标签:Java,树,同构
0
投稿
猜你喜欢
Object类toString()和equals()方法使用解析
2022-10-28 08:48:43
Java实现颜色渐变效果
2023-08-25 11:10:45
详解OpenCV For Java环境搭建与功能演示
2023-05-27 09:13:50
深入学习java8 中的CompletableFuture
2022-05-19 04:44:26
如何在Android中实现左右滑动的指引效果
2023-06-23 09:08:47
使用springCloud+nacos集成seata1.3.0搭建过程
2022-06-19 02:48:47
深入探究Spring底层核心原理
2023-03-05 08:32:16
SpringBoot实现分页功能
2021-11-07 12:33:16
Android中实现TCP和UDP传输实例
2021-11-08 14:19:59
springboot 自定义异常并捕获异常返给前端的实现代码
2022-07-23 03:09:52
Android实现调用摄像头进行拍照功能
2021-07-16 20:26:07
Android教你如何发现APP卡顿的实现
2022-06-10 22:33:45
Android控件之RatingBar自定义星级评分样式
2023-12-22 16:03:33
Android开发中amera2 Preview使用详解
2023-11-09 20:17:56
SpringBoot执行定时任务@Scheduled的方法
2022-08-13 03:43:31
springboot 防止重复请求防止重复点击的操作
2021-09-19 16:03:00
Android 微信摇一摇功能实现详细介绍
2023-06-21 21:00:09
C#算法函数:获取一个字符串中的最大长度的数字
2022-12-25 10:20:04
Windows编写jar启动脚本和关闭脚本的操作方法
2021-05-28 04:36:58
C#中Array与ArrayList用法及转换的方法
2021-07-18 13:13:23