使用Java怎么實現樹的同構

# 使用Java怎么實現樹的同構

## 1. 樹同構的概念

樹同構（Tree Isomorphism）是指兩棵樹在結構上完全相同，即可以通過重新標記節點使兩棵樹完全一致。具體來說：

- **結構相同**：忽略節點名稱時，父子關系和層級結構完全一致
- **節點映射**：存在一一對應的節點映射關系
- **應用場景**：化學分子結構比較、XML文檔結構比對、代碼AST分析等

## 2. 樹同構的判斷方法

### 2.1 基本判斷方法

1. **根節點必須相同**：如果是有根樹，根節點的度必須相同
2. **子樹匹配**：每個節點的子樹必須能找到對應匹配

### 2.2 Aho-Hopcroft-Ullman算法

經典的同構判斷算法，時間復雜度O(n)：

```java
boolean isIsomorphic(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) return true;
    if (root1 == null || root2 == null) return false;
    if (root1.children.size() != root2.children.size()) return false;
    
    // 對子樹進行匹配
    return checkChildren(root1, root2);
}

3. Java實現方案

3.1 樹節點的定義

class TreeNode {
    int val;
    List<TreeNode> children;
    
    public TreeNode(int val) {
        this.val = val;
        this.children = new ArrayList<>();
    }
    
    public void addChild(TreeNode child) {
        children.add(child);
    }
}

3.2 同構判斷實現

方法一：遞歸實現

public boolean isIsomorphic(TreeNode t1, TreeNode t2) {
    // 基本情況處理
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    if (t1.children.size() != t2.children.size()) return false;
    
    // 嘗試所有可能的子節點匹配
    for (int i = 0; i < t1.children.size(); i++) {
        boolean found = false;
        for (int j = 0; j < t2.children.size(); j++) {
            if (isIsomorphic(t1.children.get(i), t2.children.get(j))) {
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

方法二：使用規范化編碼

public boolean isIsomorphicWithCanonical(TreeNode t1, TreeNode t2) {
    String code1 = canonicalForm(t1);
    String code2 = canonicalForm(t2);
    return code1.equals(code2);
}

private String canonicalForm(TreeNode root) {
    if (root == null) return "";
    
    List<String> childCodes = new ArrayList<>();
    for (TreeNode child : root.children) {
        childCodes.add(canonicalForm(child));
    }
    
    Collections.sort(childCodes); // 排序確保順序無關
    return "(" + String.join(",", childCodes) + ")";
}

3.3 完整測試案例

public class TreeIsomorphismTest {
    public static void main(String[] args) {
        // 構建測試樹1
        TreeNode root1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        root1.addChild(node2);
        root1.addChild(node3);
        node3.addChild(node4);
        
        // 構建同構的測試樹2
        TreeNode root2 = new TreeNode(10);
        TreeNode node5 = new TreeNode(20);
        TreeNode node6 = new TreeNode(30);
        TreeNode node7 = new TreeNode(40);
        root2.addChild(node5);
        root2.addChild(node6);
        node6.addChild(node7);
        
        TreeIsomorphism checker = new TreeIsomorphism();
        System.out.println("Are isomorphic: " + 
            checker.isIsomorphic(root1, root2)); // 應輸出true
    }
}

4. 性能優化

4.1 記憶化技術

class TreeIsomorphism {
    private Map<TreeNode, String> memo = new HashMap<>();
    
    public boolean isIsomorphicMemo(TreeNode t1, TreeNode t2) {
        return canonicalForm(t1).equals(canonicalForm(t2));
    }
    
    private String canonicalForm(TreeNode node) {
        if (node == null) return "";
        if (memo.containsKey(node)) return memo.get(node);
        
        List<String> childCodes = new ArrayList<>();
        for (TreeNode child : node.children) {
            childCodes.add(canonicalForm(child));
        }
        
        Collections.sort(childCodes);
        String code = "(" + String.join(",", childCodes) + ")";
        memo.put(node, code);
        return code;
    }
}

4.2 并行處理

對于大型樹結構，可以使用并行流處理子樹：

private String parallelCanonicalForm(TreeNode node) {
    if (node == null) return "";
    
    List<String> childCodes = node.children.parallelStream()
        .map(this::canonicalForm)
        .sorted()
        .collect(Collectors.toList());
    
    return "(" + String.join(",", childCodes) + ")";
}

5. 擴展應用

5.1 處理有根樹和無根樹

對于無根樹，需要嘗試所有可能的根節點：

public boolean isIsomorphicUnrooted(TreeNode t1, TreeNode t2) {
    List<TreeNode> centers1 = findTreeCenters(t1);
    List<TreeNode> centers2 = findTreeCenters(t2);
    
    for (TreeNode c1 : centers1) {
        for (TreeNode c2 : centers2) {
            if (isIsomorphic(c1, c2)) {
                return true;
            }
        }
    }
    return false;
}

5.2 處理帶標簽的樹

如果節點有標簽需要匹配：

boolean isIsomorphicWithLabels(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    if (!t1.label.equals(t2.label)) return false;
    if (t1.children.size() != t2.children.size()) return false;
    
    // ...其余邏輯相同
}

6. 復雜度分析

• 時間復雜度：

  • 基本方法：O(n!)
  • 規范化方法：O(n log n)
  • 優化方法：O(n)

• 空間復雜度：

  • 遞歸棧：O(h)，h為樹高
  • 記憶化存儲：O(n)

7. 實際應用案例

7.1 XML文檔比較

boolean compareXMLNodes(Node node1, Node node2) {
    if (!node1.getNodeName().equals(node2.getNodeName())) return false;
    
    // 比較屬性
    NamedNodeMap attrs1 = node1.getAttributes();
    NamedNodeMap attrs2 = node2.getAttributes();
    if (attrs1.getLength() != attrs2.getLength()) return false;
    
    // 比較子節點
    NodeList children1 = node1.getChildNodes();
    NodeList children2 = node2.getChildNodes();
    if (children1.getLength() != children2.getLength()) return false;
    
    // 遞歸比較
    // ...
}

7.2 化學分子式比對

class MoleculeComparator {
    public boolean compare(Molecule m1, Molecule m2) {
        // 將分子結構轉換為樹形表示
        TreeNode t1 = convertToTree(m1);
        TreeNode t2 = convertToTree(m2);
        
        // 使用樹同構算法比較
        return new TreeIsomorphism().isIsomorphic(t1, t2);
    }
}

8. 總結

本文詳細介紹了在Java中實現樹同構判斷的多種方法，包括： 1. 基本的遞歸實現 2. 使用規范化編碼的優化方法 3. 性能優化技術（記憶化、并行處理） 4. 擴展到帶標簽樹和無根樹的處理

關鍵點總結： - 樹同構判斷的核心是子樹匹配 - 規范化編碼可以顯著提高性能 - 實際應用中需要考慮節點標簽等額外約束 - 算法選擇取決于具體場景和性能要求

完整代碼示例可在GitHub倉庫獲?。篬示例倉庫鏈接]

參考文獻

1. Aho, Hopcroft, Ullman. “The Design and Analysis of Computer Algorithms”
2. Knuth. “The Art of Computer Programming, Volume 1”
3. Java官方文檔

”`

注：實際文章約為2900字（含代碼），這里展示了核心內容框架。完整文章需要補充更多文字描述、示意圖和詳細分析。