快捷導(dǎo)航

帶你用Java方法輕松實(shí)現(xiàn)樹(shù)的同構(gòu)

更新時(shí)間：2021年06月23日 17:35:58 作者：dztom

給定兩棵樹(shù)T1和T2。如果T1可以通過(guò)若干次左右孩子互換就變成T2，則我們稱兩棵樹(shù)是“同構(gòu)”的。例如圖1給出的兩棵樹(shù)就是同構(gòu)的，因?yàn)槲覀儼哑渲幸豢脴?shù)的結(jié)點(diǎn)A、B、G的左右孩子互換后，就得到另外一棵樹(shù)

樹(shù)的同構(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,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);
    }
    //樹(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);
    }

}