使用Java怎么實現樹的同構

這篇文章主要介紹使用Java怎么實現樹的同構，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

給定兩棵樹r1、r2，如果r1可以通過若干次的左子樹和右子樹互換，使之與r2完全相同，這說明兩者同構。

舉例

樹的構造

樹可以由數組或鏈表來構造：舉例：上圖左上角的樹通過數組可表示為

該方式浪費了部分空間，但適合表示完全二叉樹

鏈表方式則比較直觀

除上述兩種方式外，還可以采用“類數組”的方式

public static class Node{String data;int left;int right;}

舉例：上圖左上角的樹可表示為

本文的樹結構使用了第三種方式

終端輸入：

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);}//樹結構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;i<N;i++){//輸入格式  data,left,rightString 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;}/*** 判斷同構* @param r1* @param r2* @return*/public boolean isomorphic(int r1,int r2,Node[] t1,Node[] t2){//須注意不要漏掉邏輯！//兩個根節點均為null，必同構if ((r1 == -1) && (r2 == -1)) {return true;}//一個非空 另一個空，必不同構if(((r1==-1)&&(r2!=-1))||((r1!=-1)&&(r2==-1))){return false;}//兩個節點非空 但值不同，必不同構if(!t1[r1].data.equals(t2[r2].data)){return false;}//兩根節點的左孩子為空條件下，則須判斷兩根節點的右子樹是否同構if(t1[r1].left==-1&&t2[r2].left==-1){return isomorphic(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))){return isomorphic(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的左子樹同構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);}}

以上是“使用Java怎么實現樹的同構”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！