在树中查找子树的简便方法

Question

我正在编写一些使用树的代码(常规树可以拥有无​​限数量的节点,但没有交叉,即两个父节点不会指向同一个子节点).无论如何,有两件事:

1)是否有任何众所周知的算法用于在树中查找子树.

2)是否有任何已实现此算法的Java库(或任何库)？即使没有,任何人都可以推荐任何好的通用Java树库吗？

我想使用这些树来保存树格式的数据,而不是它们的搜索功能.

稍微扩展一点:我正在使用树作为游戏的一部分来记录某些事件发生时会发生什么.例如,A可以击中B,可以击中两个A,可以击中另外两个A等.

这看起来像是这样的:

    A
    |
    B
   /
  A 
 / \  
A   A
   / \
  A   A

当然,不仅仅是A和B.我想要做的是(对于一个成就系统)能够告诉他们什么时候,说A已经击中了两个A:

  A
 / \
A   A

我希望能够轻松地知道第一棵树是否包含该子树.如果我不需要:)我不想编写所有代码

Answer 1

看起来像一个简单的算法:在游戏树中找到搜索树的根,并检查搜索树的子项是否是游戏树中子项的子集.

从你的解释,我不确定是否搜索树

  A
 / \
A   A

应匹配此树:

  A
 /|\
A C A

(即如果应该忽略不匹配的孩子.)

无论如何,这是我刚刚玩弄的代码.它是一个完全运行的示例,带有一个main方法和一个简单的Node类.随意玩它:

import java.util.Vector;

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

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

        partialMatch(testTree, searchTree);
    }

    private static boolean partialMatch(Node tree, Node searchTree) {
        Node subTree = findSubTreeInTree(tree, searchTree);
        if (subTree != null) {
            System.out.println("Found: " + subTree);
            return true;
        }
        return false;
    }

    private static Node findSubTreeInTree(Node tree, Node node) {
        if (tree.value == node.value) {
            if (matchChildren(tree, node)) {
                return tree;
            }
        }

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

            if (result != null) {
                if (matchChildren(tree, result)) {
                    return result;
                }
            }
        }

        return result;
    }

    private static boolean matchChildren(Node tree, Node 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 Node createTestTree() {
        Node subTree1 = new Node('A');
        subTree1.children.add(new Node('A'));
        subTree1.children.add(new Node('A'));

        Node subTree2 = new Node('A');
        subTree2.children.add(new Node('A'));
        subTree2.children.add(new Node('C'));
        subTree2.children.add(subTree1);

        Node subTree3 = new Node('B');
        subTree3.children.add(subTree2);

        Node root = new Node('A');
        root.children.add(subTree3);

        return root;
    }

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

        return root;
    }
}

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

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

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

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

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

        sb.append(')');

        return sb.toString();
    }
}