今天給大家?guī)?lái)的是如何使用Java如何實(shí)現(xiàn)樹(shù)的同構(gòu)，希望能夠給你們提供一些思路。
給定兩棵樹(shù)r1、r2，如果r1可以通過(guò)若干次的左子樹(shù)和右子樹(shù)互換，使之與r2完全相同，這說(shuō)明兩者同構(gòu)。
舉例
樹(shù)的構(gòu)造
樹(shù)可以由數(shù)組或鏈表來(lái)構(gòu)造：舉例：上圖左上角的樹(shù)通過(guò)數(shù)組可表示為
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | B | C | D | E | G | - | - | - | F | - | H | - |
該方式浪費(fèi)了部分空間，但適合表示完全二叉樹(shù)
鏈表方式則比較直觀
除上述兩種方式外，還可以采用“類數(shù)組”的方式
- public static class Node{
- String data;
- int left;
- int right;
- }
舉例：上圖左上角的樹(shù)可表示為
| 數(shù)組索引 | 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 | - | - |
本文的樹(shù)結(jié)構(gòu)使用了第三種方式
終端輸入：
A,1,2B,3,-C,-,-D,-,-A,2,1B,3,-C,-,-D,-,-
- public class TongGou {
- private Scanner scanner;
- public TongGou(){
- scanner = new Scanner(System.in);
- }
- //樹(shù)結(jié)構(gòu)
- public static class Node{
- String data;
- int left;
- int right;
- }
- /**
- * 創(chuàng)建樹(shù)
- * @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;
- }
- /**
- * 判斷同構(gòu)
- * @param r1
- * @param r2
- * @return
- */
- public boolean isomorphic(int r1,int r2,Node[] t1,Node[] t2){
- //須注意不要漏掉邏輯！
- //兩個(gè)根節(jié)點(diǎn)均為null，必同構(gòu)
- if ((r1 == -1) && (r2 == -1)) {
- return true;
- }
- //一個(gè)非空 另一個(gè)空，必不同構(gòu)
- if(((r1==-1)&&(r2!=-1))||((r1!=-1)&&(r2==-1))){
- return false;
- }
- //兩個(gè)節(jié)點(diǎn)非空 但值不同，必不同構(gòu)
- if(!t1[r1].data.equals(t2[r2].data)){
- return false;
- }
- //兩根節(jié)點(diǎn)的左孩子為空條件下，則須判斷兩根節(jié)點(diǎn)的右子樹(shù)是否同構(gòu)
- if(t1[r1].left==-1&&t2[r2].left==-1){
- return isomorphic(t1[r1].right,t2[r2].right,t1,t2);
- }
- //兩根節(jié)點(diǎn)的左孩子不為空且左孩子的值也相同，須判斷兩根節(jié)點(diǎn)的左子樹(shù)是否同構(gòu)以及兩根節(jié)點(diǎn)的右子樹(shù)是否同構(gòu)
- //如果左右子樹(shù)均同構(gòu)，則整棵樹(shù)同構(gòu)
- 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、兩根節(jié)點(diǎn)的左孩子不為空，但左孩子的值不同
- //例如：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的左子樹(shù)與r2的右子樹(shù)同構(gòu)、r1的右子樹(shù)與r2的左子樹(shù)同構(gòu)
- //故須判斷r1的左子樹(shù)是否與r2的右子樹(shù)同構(gòu),以及r1的右子樹(shù)是否與r2的左子樹(shù)同構(gòu)
- //2、兩根節(jié)點(diǎn)的左孩子一個(gè)為空，一個(gè)不為空
- //例如：r1.left==-1、r2.left!=-1，如果r2.right==-1,顯然r1的左子樹(shù)與r2的右子樹(shù)同構(gòu)，此時(shí)則有可能r1的右子樹(shù)與r2的左子樹(shù)同構(gòu)
- //故須判斷r1的左子樹(shù)是否與r2的右子樹(shù)同構(gòu),以及r1的右子樹(shù)是否與r2的左子樹(shù)同構(gòu)
- 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);
- }
- }
到此這篇關(guān)于Java如何實(shí)現(xiàn)樹(shù)的同構(gòu)?的文章就介紹到這了。
