这篇文章主要介绍使用Java怎么实现树的同构，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

给定两棵树r1、r2，如果r1可以通过若干次的左子树和右子树互换，使之与r2完全相同，这说明两者同构。

举例

树的构造

树可以由数组或链表来构造：举例：上图左上角的树通过数组可表示为

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

链表方式则比较直观

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

publicstaticclassNode{Stringdata;intleft;intright;}

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

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

终端输入：

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

publicclassTongGou{privateScannerscanner;publicTongGou(){scanner=newScanner(System.in);}//树结构publicstaticclassNode{Stringdata;intleft;intright;}/***创建树*@paramnodes*@return*/publicintcreateTree(Node[]nodes){intN=nodes.length;introot=-1;int[]check=newint[N];Arrays.fill(check,0);//初始化为0for(inti=0;i<N;i++){//输入格式data,left,rightStringnext=scanner.next();String[]inputList=next!=null?next.split(","):null;if(inputList!=null&&inputList.length==3){nodes[i]=newNode();intleft="-".equals(inputList[1])?-1:Integer.parseInt(inputList[1]);intright="-".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(inti=0;i<check.length;i++){if(check[i]==0&&nodes[i].data!=null){root=i;break;}}returnroot;}/***判断同构*@paramr1*@paramr2*@return*/publicbooleanisomorphic(intr1,intr2,Node[]t1,Node[]t2){//须注意不要漏掉逻辑！//两个根节点均为null，必同构if((r1==-1)&&(r2==-1)){returntrue;}//一个非空另一个空，必不同构if(((r1==-1)&&(r2!=-1))||((r1!=-1)&&(r2==-1))){returnfalse;}//两个节点非空但值不同，必不同构if(!t1[r1].data.equals(t2[r2].data)){returnfalse;}//两根节点的左孩子为空条件下，则须判断两根节点的右子树是否同构if(t1[r1].left==-1&&t2[r2].left==-1){returnisomorphic(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))){returnisomorphic(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的左子树同构returnisomorphic(t1[r1].left,t2[r2].right,t1,t2)&&isomorphic(t1[r1].right,t2[r2].left,t1,t2);}}publicstaticvoidmain(String[]args){TongGoutongGou=newTongGou();Node[]nodes=newNode[4];Node[]nodes1=newNode[4];inttree1=tongGou.createTree(nodes);System.out.println();inttree2=tongGou.createTree(nodes1);booleanisomorphic=tongGou.isomorphic(tree1,tree2,nodes,nodes1);System.out.println(isomorphic);}}

以上是“使用Java怎么实现树的同构”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！