java 在树中查找子树的简单方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/584696/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Easy way to find Subtree in a Tree
提问by cdmckay
I'm writing some code that uses a Tree (a regular tree that can have an unlimited number of nodes, but no crossover, i.e. two parent nodes will not point the the same child node). Anyway, two things:
我正在编写一些使用树的代码（一个可以有无限数量节点的常规树，但没有交叉，即两个父节点不会指向同一个子节点）。总之，有两点：
1) Are there any well-known algorithms for finding a sub-tree within a tree.
1）是否有任何众所周知的算法可以在树中找到子树。
2) Are there any Java libraries (or any libraries for that matter) that already implement this algorithm? Even if there are none, can anyone recommend any good general purpose Java tree library?
2) 是否有任何已经实现此算法的 Java 库（或任何与此相关的库）？即使没有，任何人都可以推荐任何好的通用 Java 树库吗？
I want to use these trees for holding data in a tree format, not for their searching capabilities.
我想使用这些树以树格式保存数据，而不是为了它们的搜索功能。
To expand a bit: I'm using the tree as part of game to keep a history of what happens when a certain events happen. For example, an A can hit a B which can hit two A's which can hit another two A's etc.
稍微扩展一下：我使用树作为游戏的一部分来保存特定事件发生时发生的事情的历史记录。例如，A 可以击中 B，B 可以击中两个 A，然后可以击中另外两个 A，等等。
That would look something like:
那看起来像：
A
|
B
/
A
/ \
A A
/ \
A A
Of course there's more than just A and B. What I want to do is (for an achievement system) is be able to tell when, say an A has hit two A's:
当然，不仅仅是 A 和 B。我想要做的是（对于成就系统）能够判断何时，比如一个 A 击中了两个 A：
A
/ \
A A
I want to be able to easily know if the first tree contains that subtree. And I don't want to have to write all the code for doing so if I don't have to :)
我希望能够轻松知道第一棵树是否包含该子树。如果我不需要，我不想编写所有代码来这样做:)
回答by gclj5
Looks like a straightforward algorithm: Find the root of the search tree in the game tree and check whether the children of the search tree are a subset of the children in the game tree.
看起来很简单的算法：在博弈树中找到搜索树的根，并检查搜索树的孩子是否是博弈树中孩子的子集。
From your explanations, I'm not sure whether the search tree
根据您的解释，我不确定搜索树是否
A
/ \
A A
should match this tree:
应该匹配这棵树：
A
/|\
A C A
(i.e. if non-matching children are supposed to be ignored.)
（即，如果不匹配的孩子应该被忽略。）
Anyway, here's the code I just toyed around with. It's a fully running example and comes with a main method and a simple Nodeclass. Feel free to play with it:
无论如何，这是我刚刚玩弄的代码。这是一个完全运行的示例，并带有一个 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();
}
}
回答by Martin
Are you looking for any particular constraints on a subtree? If not, a simple traversal should suffice for identifying subtrees (basically treat each node as the root of a subtree).
您是否正在寻找对子树的任何特定约束？如果不是，简单的遍历应该足以识别子树（基本上将每个节点视为子树的根）。
I believe you'll find that the API you'll want for a tree varies a great deal by your particular application -- so much that generic implementations are not very useful. Perhaps if you could tell us what kind of application the tree will be used for, we could provide particulars.
我相信您会发现树所需的 API 因您的特定应用程序而异——以至于通用实现不是很有用。也许如果您能告诉我们该树将用于哪种应用程序，我们可以提供详细信息。
Also, if you're justusing a tree for data storage, you might want to ask yourself why you need a tree. That answer should also answer the question in my previous paragraph.
此外，如果您只是将树用于数据存储，您可能想问问自己为什么需要一棵树。这个答案也应该回答我上一段中的问题。
回答by Ken
I wonder if there's an extension of the Knuth algorithm that would be more efficient than a naive traversal...
我想知道是否有 Knuth 算法的扩展比朴素的遍历更有效......
回答by Dick King
If there is one big, static, tree and you will be searching for many subtrees in the same big tree, you might want to annotate each node with the set of hashes of all of its subtrees to a given depth depending on how much storage you're willing to expend on that functionality. Then build a map from hash values to the set of nodes that are roots of a subtree with that hash value. Then just check each one of those, presumably much cheaper than a traversal, for the hash of the root of the query tree to that same depth.
如果有一个大的、静态的树，并且您将在同一棵大树中搜索许多子树，您可能希望使用其所有子树的散列集将每个节点注释到给定深度，具体取决于您的存储量'愿意花费在该功能上。然后构建从哈希值到具有该哈希值的子树根节点集的映射。然后只需检查其中的每一个，大概比遍历便宜得多，查询树根的哈希值是否相同。
