Tìm tất cả các subtrees trong một cây phù hợp với một cây con đã cho trong Java

Question

Tôi đang viết mã bằng Java sử dụng cây có gốc, không có thứ tự nơi mỗi nút có thể có bất kỳ số lượng nút con nào. Với một cây T và một cây con S, tôi muốn có thể tìm thấy tất cả các subtrees trong T phù hợp với S (đó là tất cả các subtrees trong T đó là đẳng cấu với S).

Một cây con của T là đẳng cấu với S, nếu các nút của S có thể được ánh xạ tới các nút của T theo cách như vậy mà các cạnh của bản đồ S để cạnh trong T.

Một previous question đã được yêu cầu trên làm thế nào để tìm thấy nếu một cây có chứa một cây con khác tuy nhiên tôi muốn để có thể tìm thấy TẤT CẢ subtrees trong T khớp với S. Ngoài ra tôi muốn có thể ánh xạ từ mỗi nút trong mỗi trận đấu trong T đến nút tương ứng trong S

Tức là, khi kết hợp được tìm thấy, nó sẽ được trả về không đơn giản như một con trỏ tới nút trong T, trong đó một cây được bắt rễ phù hợp với S, nhưng khớp sẽ được trả về như là somethi ng như một danh sách các cặp con trỏ tới các nút [(T1, S1), (T2, S2), ... (Tn, Sn)] sao cho T1 là một con trỏ tới một nút trong T ánh xạ tới nút S1 trong subtree và như vậy.

Hoặc đơn giản là danh sách các cặp giá trị có thể được trả về vì mỗi nút trong cây T và cây con S có một số nguyên duy nhất liên kết với nó.

Ví dụ:

Với T cây như sau:

a 
/\ 
    b c 
/\ 
d e 

và cây con S như:

x 
/\ 
    y z 

danh sách sau các trận đấu sẽ được trả lại:

[(a, x), (b, y), (c, z)] [(b, x), (d, y), (e, z)]

Một trận đấu duy nhất được xác định bởi tập hợp các nút trong T, không ánh xạ giữa các nút trong T và S.

Vì vậy, các trận đấu sau đây:

[(a, x), (b, z), (c, y)]

được coi là bản sao của

[(a, x), (b, y), (c, z)]

bởi vì họ có cùng một tập hợp các nút từ T (a, b, c) do đó chỉ một trong các kết quả phù hợp sẽ được trả lại.

Một ví dụ khác, đưa ra cây T:

a 
    /|\ 
    b c d 

và cây con S:

x 
/\ 
y z 

danh sách sau các trận đấu sẽ được trả lại:

[(a, x), (b, y), (c, z)] [(a, x), (b, y), (d, z)] [(a, x), (c, y), (d , z)]

Có ai có thể cung cấp bất kỳ mã ví dụ nào về cách thực hiện việc này không?

Chỉnh sửa (liên quan đến bình luận Chris Kannon của):

Tôi đang nghĩ đến bạn muốn một ai đó để mã câu trả lời cho bạn? Bạn đã nhận được bao nhiêu? Bạn viết mã gì? - Chris Kannon 1 giờ trước

Tôi có đoạn code sau đây mà khi chạy, xây dựng một danh sách (matchesList) của con trỏ đến nút trong cây nơi subtrees được bắt rễ phù hợp với cây con nhất định. Tuy nhiên, có thể có nhiều subtrees bắt nguồn từ cùng một nút và hiện tại mỗi nút sẽ chỉ được thêm nhiều nhất một lần vào matchList bất kể số lượng kết quả trùng khớp được bắt nguồn từ đó.

Ngoài ra, tôi không thể tìm cách xây dựng bản đồ được mô tả ở trên giữa các nút trong cây con và các nút trong kết quả phù hợp được tìm thấy trong cây gốc.

package Example; 

import java.util.LinkedList; 
import java.util.Vector; 

public class PartialTreeMatch { 
    public static void main(String[] args) { 
     NodeX testTree = createTestTree(); 
     NodeX searchTree = createSearchTree(); 

     System.out.println(testTree); 
     System.out.println(searchTree); 

     partialMatch(testTree, searchTree); 
    } 

    static LinkedList<NodeX> matchesList = new LinkedList<NodeX>(); 

    private static boolean partialMatch(NodeX tree, NodeX searchTree) { 
     findSubTreeInTree(tree, searchTree); 
     System.out.println(matchesList.size()); 
     for (NodeX n : matchesList) { 
      if (n != null) { 
       System.out.println("Found: " + n); 
      } 
     } 

     return false; 
    } 

    private static NodeX findSubTreeInTree(NodeX tree, NodeX node) { 
     if (tree.value == node.value) { 
      if (matchChildren(tree, node)) { 
       matchesList.add(tree); 

      } 
     } 

     NodeX result = null; 
     for (NodeX child : tree.children) { 
      result = findSubTreeInTree(child, node); 

      if (result != null) { 
       if (matchChildren(tree, result)) { 
        matchesList.add(result); 

       } 
      } 
     } 

     return result; 
    } 

    private static boolean matchChildren(NodeX tree, NodeX searchTree) { 
     if (tree.value != searchTree.value) { 
      return false; 
     } 

     if (tree.children.size() < searchTree.children.size()) { 
      return false; 
     } 

     boolean result = true; 
     int treeChildrenIndex = 0; 

     for (int searchChildrenIndex = 0; searchChildrenIndex < searchTree.children 
       .size(); searchChildrenIndex++) { 

      // Skip non-matching children in the tree. 
      while (treeChildrenIndex < tree.children.size() 
        && !(result = matchChildren(tree.children 
          .get(treeChildrenIndex), searchTree.children 
          .get(searchChildrenIndex)))) { 
       treeChildrenIndex++; 
      } 

      if (!result) { 
       return result; 
      } 
     } 

     return result; 
    } 

    private static NodeX createTestTree() { 

     NodeX subTree2 = new NodeX('A'); 
     subTree2.children.add(new NodeX('A')); 
     subTree2.children.add(new NodeX('A')); 

     NodeX subTree = new NodeX('A'); 
     subTree.children.add(new NodeX('A')); 
     subTree.children.add(new NodeX('A')); 
     subTree.children.add(subTree2); 

     return subTree; 
    } 

    private static NodeX createSearchTree() { 
     NodeX root = new NodeX('A'); 
     root.children.add(new NodeX('A')); 
     root.children.add(new NodeX('A')); 

     return root; 
    } 
} 

class NodeX { 
    char value; 
    Vector<NodeX> children; 

    public NodeX(char val) { 
     value = val; 
     children = new Vector<NodeX>(); 
    } 

    public String toString() { 
     StringBuilder sb = new StringBuilder(); 

     sb.append('('); 
     sb.append(value); 

     for (NodeX child : children) { 
      sb.append(' '); 
      sb.append(child.toString()); 
     } 

     sb.append(')'); 

     return sb.toString(); 
    } 
} 

Đoạn mã trên cố gắng tìm tất cả các đồ thị con trong:

A 
/|\ 
A A A 
/\ 
    A A 

mà trận đấu:

A 
/\ 
    A A 

Mã phát hiện thành công rằng có một trận đấu bắt nguồn từ một nút đầu trong cây đầu tiên và đứa thứ 3 của cây đầu tiên. Tuy nhiên, thực tế có 3 trận đấu bắt nguồn từ nút trên cùng, không chỉ là một. Ngoài ra, mã không xây dựng một ánh xạ giữa các nút trong cây và các nút trong cây con và tôi không thể tìm ra cách để làm điều này.

Có ai có thể đưa ra lời khuyên nào về cách thực hiện việc này không?

Answer 1

Tôi nghĩ rằng phương pháp đệ quy của bạn cần phải trả về một danh sách các phần khớp, thay vì chỉ là một boolean. Điều đó sẽ đi một chặng đường dài để giải quyết cả hai vấn đề của bạn (sự cần thiết phải trả lại danh sách các trận đấu, cũng như tìm kiếm nhiều trận đấu).

Java giống như mã giả cho hàm đệ quy có thể trông như thế này:

findMatches(treeNode, searchNode) { 
    if searchNode has no children { 
     // search successful 
     pairs = [] // empty list 
     return [pairs] // list of lists 
    } 
    else { 
     matches = [] // empty list 
     searchChild = first child node of searchNode 
     searchNode2 = searchNode with searchChild removed 
     // NOTE: searchNode2 is created by doing a shallow copy of just the node 
     // (not it's children) and then removing searchChild from the child list. 

     for each treeChild in treeNode.children { 
      if treeChild.value == searchChild.value { 
       treeNode2 = treeNode with treeChild removed // also a shallow copy 
       childMatches = findMatches(searchChild, treeChild) 
       nodeMatches = findMatches(treeNode2, searchNode2) 

       // cross-product 
       for each nodeMatchPairs in nodeMatches { 
        for each childMatchPairs in childMatches { 
         fullMatchPairs = [(searchChild, treeChild)] 
          + childMatchPairs + nodeMatchPairs // concatenate lists 
         add fullMatchPairs to matches 
        } 
       } 
      } 
     } 

     return matches 
    } 
} 

Chú ý rằng chức năng này không kiểm tra treeNode.value == searchNode.value, hoặc thêm video này vào danh sách. Người gọi cần làm điều đó. Hàm này cần được chạy ở mọi nút của cây.

Như thiết kế hiện tại, nó có thể sử dụng quá nhiều bộ nhớ, nhưng điều đó có thể được tối ưu hóa.

Answer 2

This có thể hữu ích.