文档章节

树的同构 java

o
 osc_z1hvg4cu
发布于 2018/04/24 18:06
字数 476
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>


import
java.util.Scanner; //创造节点类型 class Node { String key; int left; int right; } class test { public static void main(String[] args) { Scanner sc=new Scanner(System.in); Node[] arr1=new Node[8]; Node[] arr2=new Node[8]; int head1=biuldTree(arr1, sc); int head2=biuldTree(arr2, sc); boolean result=isTonggou(arr1,head1,arr2,head2); if (result) { System.out.print("Yes"); } else { System.out.print("No"); } } public static int biuldTree(Node[] arr,Scanner sc) { int N=sc.nextInt(); String templeft; String tempright; int[] flag=new int[N]; int root=0; for (int i=0;i<N ;i++ ) { Node node=new Node(); node.key=sc.next(); templeft=sc.next(); tempright=sc.next(); arr[i]=node; if (templeft.equals("-")) { node.left=-1; } else { node.left=Integer.parseInt(templeft); flag[node.left]=1; } if (tempright.equals("-")) { node.right=-1; } else { node.right=Integer.parseInt(tempright); flag[node.right]=1; } for (int j=0;j<N ;j++ ) { if (flag[j]==0) { root=j; } } } return root; } public static boolean isTonggou(Node[] arr1,int head1,Node[] arr2,int head2) { //递归出口 if ((head1==-1) &&( head2==-1)) {return true;} if ((head1==-1) && (head2 !=-1) || (head1!=-1) && (head2==-1)) {return false;} if (!(arr1[head1].key.equals(arr2[head2].key))) {return false;} //树1和树2的左孩子都为空,判断右孩子为根节点的树是不是同构 if ((arr1[head1].left==-1) && (arr2[head2].left==-1)) { return isTonggou(arr1,arr1[head1].right, arr2, arr2[head2].right); } //如果树1的左孩子不空,树2的左孩子也不空,并且两个左孩子的key相等,那么判断以左孩子为根的树是否同构,以右孩子为根的树是否同构 if ((arr1[head1].left != -1 )&&( arr2[head2].left != -1 )&& (arr1[arr1[head1].left].key.equals((arr2[arr2[head2].left].key)) )) { return (isTonggou(arr1, arr1[head1].left,arr2, arr2[head2].left)&&(isTonggou(arr1,arr1[head1].right,arr2,arr2[head2].right))); } //如果上述都不满足,那么判断以树1的左孩子和树2的右孩子为根的树是否同构,判断以树1的右孩子和树2的左孩子为根的树是否同构 else { return (isTonggou(arr1, arr1[head1].left,arr2, arr2[head2].right)&&(isTonggou(arr1,arr1[head1].right,arr2,arr2[head2].left))); } } }

实验结果

采用结构数组来储存节点,将孩子为空标记为-1.

Yes和No前面的树分别标记两颗树的根所在的位置,是我调试时加上以便判断哪个地方出问题的。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
PTA——03-树1 树的同构(25 分)【java语言实现】

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

osc_jnyhv0pz
2018/04/21
1
0
Json字段选取器介绍和实现

最近为了工作方便写了一个小工具,这个小工具作用很简单,就是从一个json字符串中筛出你想要的部分。 介绍 背景是这样的,我们为了线上调试方便,有个工具可以模拟发起一次数据请求,然后将结...

xindoo
06/23
2
0
LeetCode:Isomorphic Strings - 同构的字符串

1、题目名称 Isomorphic Strings(同构的字符串) 2、题目地址 https://leetcode.com/problems/isomorphic-strings/ 3、题目内容 英文: Given two strings s and t, determine if they are......

北风其凉
2015/08/08
1.4K
0
ShardingJDBC源码分析系列1:概览

参考文档: https://shardingsphere.apache.org/document/current/cn/overview/ --- ShardingSphere是一套开源的分布式数据库中间件解决方案组成的生态圈,它由Sharding-JDBC、Sharding-Prox...

强子大叔的码田
01/24
0
0
20172303 2017-2018-2 《程序设计与数据结构》第10周学习总结

教材学习内容总结 1.集合 定义:专门用于保存信息的对象。 集合的同构和异构: 同构:集合中保存的类型全部相同。 异构:集合中可以保存全部的类型。 2.数据结构 数据结构分类: 动态数据结构...

osc_xb4v1nhl
2018/05/19
2
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux系统检查用户账户到期时间

如果你在 Linux 上启用了密码策略。密码必须在到期前进行更改,并且登录到系统时会收到通知。如果你很少使用自己的帐户,那么可能由于密码过期而被锁定。在许多情况下,这可能会在无需密码登...

老孟的Linux私房菜
57分钟前
17
0
关于南京哪里有开餐饮费发票?

关于南京哪里有开餐饮费发票?聚焦餐饮行业,谈话〖18 7一電一7 5 3 8一徴一3331〗研究院昨发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元.随着餐饮行业的快速...

点击fojewio
今天
7
0
android studio 4.0 打开DDMS

1、先找到AndroidStudio配置的SDK路径; 2、在SDK的/tools/路径下有个monitor.bat 的批处理文件; 3、鼠标连续点击两下monitor.bat这个批处理文件,在屏幕上会打开一个类似CMD的命令行中输入...

chenhongjiang
今天
10
0
如何在Android中使用SharedPreferences来存储,获取和编辑值

问题: Closed . 已关闭 。 This question needs to be more focused. 这个问题需要更加集中。 It is not currently accepting answers. 它当前不接受答案。 Learn more . 了解更多 。 Want...

fyin1314
今天
6
0
【JDK1.8】LinkedList源码分析

LinkedList的特性 LinkedList内部使用双向链表作为存储结构,LinkedList可以理解为链表的扩展对象,封装了常用的和非常用的操作链表的方法。以及在通过索引获取元素时的简单优化,通常Linke...

XuePeng77
今天
40
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部