java在树中查找子树的简单方法

Question

我正在编写一些使用树的代码（可以有无限个节点但没有交叉的常规树，即两个父节点不会指向同一个子节点）。无论如何，有两件事：

1）是否有在树中查找子树的已知算法

2）是否有任何Java库（或与此相关的库）已经实现了该算法？即使没有，有人能推荐任何好的通用Java树库吗

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

更进一步：我使用树作为游戏的一部分来记录特定事件发生时发生的事情。例如，A可以击中B，B可以击中两个A，A可以击中另外两个A，等等

这看起来像：

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

当然不仅仅是A和B。我想做的是（对于成就系统而言）能够判断A何时达到两个A：

  A
 / \
A   A

我希望能够轻松地知道第一棵树是否包含该子树。如果不需要的话，我也不想写所有这样做的代码：）

Answer 1

您是否在子树上查找任何特定约束？如果不是，则simple traversal应足以识别子树（基本上将每个节点视为子树的根）

我相信您会发现，树所需的API因您的特定应用程序而有很大差异，以至于通用实现不是很有用。也许如果你能告诉我们这棵树将用于什么样的应用，我们可以提供细节

另外，如果您正使用一棵树来存储数据，您可能会问自己为什么需要一棵树。这个答案也应该回答我上一段的问题

Answer 2

我想知道Knuth算法是否有一个比简单遍历更有效的扩展

Answer 3

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

根据你的解释，我不确定搜索树

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

Answer 4

如果有一棵大的静态树，并且您将在同一棵大树中搜索多个子树，那么您可能希望使用其所有子树的哈希集对每个节点进行注释，注释深度取决于您愿意在该功能上花费的存储量。然后构建一个从散列值到具有该散列值的子树根节点集的映射。然后只需检查其中的每一个，大概比遍历便宜得多，以便将查询树的根散列到相同的深度