锐客网

  1. 首页 > it技术 > >

Java如何实现树的同构?

树的同构 备忘！
定义：给定两棵树r1、r2，如果r1可以通过若干次的左子树和右子树互换，使之与r2完全相同，这说明两者同构。
举例
Java如何实现树的同构?
文章图片

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

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); //初始化为0for (int i=0; i0) {check[left] = 1; }if(right>0){check[right] = 1; }}}for(int i=0; i
【Java如何实现树的同构?】到此这篇关于Java如何实现树的同构?的文章就介绍到这了,更多相关Java实现树的同构内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

    推荐阅读


    上一篇：基于JavaScript实现省市联动效果

    下一篇：基于JavaScript实现年月日三级联动