在Java中查找与给定子树匹配的树中所有子树

Question

我正在使用Java编写代码，该代码使用无序的根树，每个节点可能有任意数量的子节点。给定树T和子树S，我希望能够找到所有与S匹配的T中的子树（即与S同构的T中的所有子树）。

如果T的一个子树与S同构，则S的节点可以映射到T的节点，使得S的边映射到T中的边。

关于如何查找树是否包含另一个子树，已经有一个previous question，但是我想要能够找到T中与S匹配的所有子树。此外，我希望能够将每个匹配中T中的每个节点映射到S中相应的节点。

也就是说，当找到匹配时，它不仅应返回指向T中根据S匹配的树的节点的指针，而且应该返回类似于指向节点对的列表 [(T1,S1),(T2,S2),...(Tn,Sn)] 的匹配，其中T1是指向在子树中映射到节点S1的T中的节点的指针，依此类推。

或者，可以简单地返回一对值的列表，因为树T和子树S中的每个节点都与其唯一的整数标识符相关联。

例如：

给定树T如下：

    a
   / \
  b   c
 / \  
d   e

并且子树S为：

    x
   / \
  y   z

应返回以下匹配列表：

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

唯一的匹配是由T中的节点集确定的，而不是T和S之间的映射关系。

因此，以下匹配：

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

被视为与

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

重复，因为它们具有相同的来自T的节点集（a，b，c），因此只应返回其中一个匹配。

作为另一个示例，给定树T：

    a
   /|\
  b c d

和子树S：

  x
 / \  
y   z

以下匹配列表应返回：

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

有人能提供任何如何完成这个任务的示例代码吗？

编辑（与Chris Kannon的评论相关）：

我想你想让别人为你编码答案？你做到了多远？你写了什么代码？- Chris Kannon 1小时前

我有以下代码，当运行时，建立一个指向树中匹配给定子树的子树根节点的指针列表（matchesList）。但是，在同一节点处可能有多个以相同方式匹配的子树，并且当前每个节点最多只会添加一次到matchesList中，无论有多少匹配项在那里。

此外，我无法弄清楚如何建立上述在子树中的节点和在原始树中找到的匹配节点之间的映射。

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();
    }
}

上述代码试图在以下内容中找到所有的子图：

  A
 /|\  
A A A
   / \
  A   A

匹配哪些:

    A
   / \
  A   A

代码成功检测到第一棵树的顶部节点和第一棵树的第三个子节点存在匹配。然而，实际上有3个与顶部节点匹配的子树，而不仅仅是一个。此外，代码没有建立树中节点和子树中节点之间的映射，我无法弄清如何实现这一点。

有人可以提供如何做到这一点的建议吗？

- tree-hacker

---

你是想让别人为你编写答案吗？你已经做到哪一步了？你写了什么代码？ - Chris Kannon

+1 给一个很好的解释.. 其实今天已经没有投票了，但意图是最重要的。 - Anurag

@Chris Kannon：我已根据您的评论更新了问题，并包含了到目前为止编写的代码。 - tree-hacker

Answer 1

我认为您的递归方法需要返回一个部分匹配列表，而不仅仅是布尔值。这将大大有助于解决您的两个问题（需要返回匹配列表以及查找多个匹配项）。

对于递归函数，类似Java的伪代码可能如下所示：

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
    }
}

请注意，此函数不会测试treeNode.value == searchNode.value，也不会将其添加到列表中。调用者需要自行完成这一步骤。此函数需要在树的每个节点上运行。

目前设计的方式可能使用了过多的内存，但可以进行优化。

- Todd Owen

Answer 2

这个可能会有帮助。

- witzar

---

谢谢。是的，我已经阅读了关于树同构的那些注释和有关子树同构的附加幻灯片（http://www.lsi.upc.es/~valiente/riga-tre.pdf），但我无法弄清楚如何将所给算法转换为代码，特别是在如何建立子树中节点和树匹配中节点之间映射方面。您有什么想法吗？ - tree-hacker

有人有最新的链接吗？ 给定的链接失效了（404）。 - douira