今天给大家带来的是关于Java的相关知识,文章围绕着Java如何实现树的同构展开,文中有非常详细的介绍及代码示例,需要的朋友可以参考下
树的同构
备忘！
定义：给定两棵树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;i0) { check[left] = 1; } if(right>0){ check[right] = 1; } } } for(int i=0;i 到此这篇关于Java如何实现树的同构?的文章就介绍到这了,更多相关Java实现树的同构内容请搜索html中文网以前的文章或继续浏览下面的相关文章希望大家以后多多支持html中文网！
以上就是Java如何实现树的同构?的详细内容，更多请关注0133技术站其它相关文章！
