我正在编写一些使用树的代码（可以有无限数量的节点但没有交叉的常规树，即两个父节点不会指向同一个子节点）。总之，有两点：
1）是否有任何众所周知的算法可以在树中找到子树。
2）是否有任何Java库（或任何库）已经实现了这个算法？即使没有，任何人都可以推荐任何好的通用 Java 树库吗？
我想使用这些树来保存树格式的数据，而不是它们的搜索功能。
扩展一点：我将树用作游戏的一部分，以记录特定事件发生时所发生的情况。例如，一个 A 可以击中一个 B，该 B 可以击中两个 A，而该 B 可以击中另外两个 A，等等。
这看起来像：
A
|
B
/
A
/ \
A A
/ \
A A
当然，不仅仅是 A 和 B。我想要做的是（对于成就系统）能够判断什么时候，比如说一个 A 达到了两个 A：
A
/ \
A A
我希望能够轻松知道第一棵树是否包含该子树。如果我不需要的话，我不想写所有的代码来这样做:)
看起来很简单的算法：在博弈树中找到搜索树的根，并检查搜索树的子节点是否是博弈树中子节点的子集。
根据您的解释，我不确定搜索树是否
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();
}
}
您是否正在寻找对子树的任何特定约束？如果不是，一个简单的遍历应该足以识别子树（基本上将每个节点视为子树的根）。
我相信你会发现你想要的树的 API 会因你的特定应用程序而变化很大——以至于通用实现并不是很有用。也许如果你能告诉我们这棵树将用于什么样的应用程序，我们可以提供细节。
此外，如果您只是使用树来存储数据，您可能想问自己为什么需要树。这个答案也应该回答我上一段中的问题。
我想知道 Knuth 算法的扩展是否比简单的遍历更有效......
如果有一个大的静态树，并且您将在同一棵大树中搜索许多子树，您可能希望使用其所有子树的哈希集注释每个节点到给定深度，具体取决于您的存储量'愿意花费在那个功能上。然后构建一个从哈希值到节点集的映射，这些节点是具有该哈希值的子树的根节点。然后只需检查每一个，可能比遍历便宜得多，查询树的根的哈希到相同的深度。