我正在编写一些代码，使用树(Tree)（一个常规的树形结构，可以拥有无限数量的节点，但没有交叉，即两个父节点不会指向同一个子节点）。无论如何，需要解决两个问题：
1）是否有已知的算法可以在树中查找子树。
2）是否有任何Java库（或任何其他库）已经实现了这个算法？ 即使没有，有没有人推荐好的通用Java树库？
我想使用这些树以树形式存储数据，而不是为了它们的搜索功能。
稍作说明：我正在将树作为游戏的一部分，以保留发生某些事件时发生的历史记录。例如，A可以打B，B可以打两个A，然后可以再打两个A等等。
这将类似于：
A
|
B
/
A
/ \
A A
/ \
A A
A
/ \
A A
我希望能够轻松地知道第一棵树是否包含该子树。如果不必要的话，我不想自己编写所有执行此操作所需的代码 :)
看起来是一个简单的算法：在游戏树中找到搜索树的根节点，并检查搜索树的子节点是否是游戏树中子节点的子集。
从你的解释中，我不确定搜索树是什么。
A
/ \
A A
应该匹配这棵树：
A
/|\
A C A
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();
}
}
我想知道是否有Knuth算法的扩展能比朴素遍历更有效率...