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

Question

我在Java中编写代码,使用无序的根树,其中每个节点可以有任意数量的子节点.给定树T和子树S,我希望能够找到T中与S匹配的所有子树(即T中与S同构的所有子树).

如果S的节点可以映射到T的节点,使得S的边缘映射到T中的边缘,则T的子树与S同构.

一个先前的问题已经被问如何找到如果树包含另一个子树,但是我希望能够找到所有 T中的子树匹配的S.此外,我希望能够从每个节点在T映象在每场比赛S中的对应节点

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

或者,可以返回简单的值对列表,因为树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个子节点存在匹配.但是,实际上有3个匹配在顶层节点,而不仅仅是一个.此外,代码不会在树中的节点和子树中的节点之间建立映射,我无法弄清楚如何执行此操作.

任何人都可以就如何做到这一点提出任何建议吗？

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,或将其添加到列表中.来电者需要这样做.此函数需要在树的每个节点上运行.

按照目前的设计,它可能会占用太多内存,但可以进行优化.