在Java中查找树中与给定子树匹配的所有子树
https://stackoverflow.com/questions/2101914
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在用 Java 编写代码，该代码使用无序的有根树，其中每个节点可能有任意数量的子节点。给定一棵树 T 和一棵子树 S，我希望能够找到 T 中与 S 匹配的所有子树（即 T 中与 S 同构的所有子树）。
如果 S 的节点可以通过 S 的边映射到 T 中的边的方式映射到 T 的节点，则 T 的子树与 S 同构。
A 上一个问题 有人询问如何查找一棵树是否包含另一个子树，但是我希望能够找到 全部 T 中与 S 匹配的子树。另外，我希望能够将 T 中每个匹配中的每个节点映射到 S 中的相应节点。
也就是说，当找到匹配项时，它不应该简单地作为指向 T 中与 S 匹配的树的根节点的指针返回，而应该以类似于指向节点的指针对的列表的形式返回。 (T1,S1),(T2,S2),...(Tn,Sn)]，这样 T1 是指向 T 中节点的指针，该节点映射到子树中的节点 S1，依此类推。
或者，可以简单地返回值对的列表，因为树 T 和子树 S 中的每个节点都有与其关联的唯一整数标识符。
例如：
给定树 T 如下：
a
/ \
b c
/ \
d e
子树 S 为：
x
/ \
y z
应返回以下匹配列表：
（a，x），（b，y），（c，z）] [（b，x），（d，y），（e，z）
唯一匹配由 T 中的节点集确定， 不是 T 和 S 中的节点之间的映射。
所以下面的匹配：
[(a,x),(b,z），（C，y)]
被认为是重复的
[(a,x),(b,y），（C，z)]
因为它们具有来自 T (a,b,c) 的相同节点集，因此只应返回其中一个匹配项。
另一个例子，给定树 T：
a
/|\
b c d
和子树S：
x
/ \
y z
应返回以下匹配列表：
（a，x），（b，y），（c，z）] [（a，x），（b，y），（d，z）] [（a，x），（c，c，y） ，（D，Z）
谁能给出如何执行此操作的示例代码？
编辑（关于克里斯·卡农的评论）：
我想您要有人为您编码答案吗？你走了多远？你写了什么代码？- 克里斯·坎农（Chris Kannon）1小时前
我有以下代码，运行时会构建指向树中节点的指针列表（matchesList），其中子树以与给定子树匹配的根为根。然而，可能有多个子树以同一节点为根，并且当前每个节点最多只能添加到 matchesList 一次，无论有多少匹配项以该节点为根。
此外，我无法弄清楚如何在子树中的节点与原始树中找到的匹配中的节点之间建立上述映射。
package Example;
import java.util.LinkedList;
import java.util.Vector;
public class PartialTreeMatch {
public static void main(String[] args) {
NodeX testTree = createTestTree();
NodeX searchTree = createSearchTree();
System.out.println(testTree);
System.out.println(searchTree);
partialMatch(testTree, searchTree);
}
static LinkedList<NodeX> matchesList = new LinkedList<NodeX>();
private static boolean partialMatch(NodeX tree, NodeX searchTree) {
findSubTreeInTree(tree, searchTree);
System.out.println(matchesList.size());
for (NodeX n : matchesList) {
if (n != null) {
System.out.println("Found: " + n);
}
}
return false;
}
private static NodeX findSubTreeInTree(NodeX tree, NodeX node) {
if (tree.value == node.value) {
if (matchChildren(tree, node)) {
matchesList.add(tree);
}
}
NodeX result = null;
for (NodeX child : tree.children) {
result = findSubTreeInTree(child, node);
if (result != null) {
if (matchChildren(tree, result)) {
matchesList.add(result);
}
}
}
return result;
}
private static boolean matchChildren(NodeX tree, NodeX 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 NodeX createTestTree() {
NodeX subTree2 = new NodeX('A');
subTree2.children.add(new NodeX('A'));
subTree2.children.add(new NodeX('A'));
NodeX subTree = new NodeX('A');
subTree.children.add(new NodeX('A'));
subTree.children.add(new NodeX('A'));
subTree.children.add(subTree2);
return subTree;
}
private static NodeX createSearchTree() {
NodeX root = new NodeX('A');
root.children.add(new NodeX('A'));
root.children.add(new NodeX('A'));
return root;
}
}
class NodeX {
char value;
Vector<NodeX> children;
public NodeX(char val) {
value = val;
children = new Vector<NodeX>();
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('(');
sb.append(value);
for (NodeX child : children) {
sb.append(' ');
sb.append(child.toString());
}
sb.append(')');
return sb.toString();
}
}
上面的代码尝试查找以下位置的所有子图：
A
/|\
A A A
/ \
A A
哪个匹配：
A
/ \
A A
该代码成功检测到存在以第一棵树的顶部节点和第一棵树的第三个子节点为根的匹配。然而，实际上有 3 个匹配项以顶部节点为根，而不仅仅是 1 个。此外，代码不会在树中的节点和子树中的节点之间建立映射，我无法弄清楚如何做到这一点。
任何人都可以提供有关如何执行此操作的任何建议吗？
解决方案
我认为你的递归方法需要返回部分匹配的列表，而不仅仅是一个布尔值。这将大大有助于解决您的两个问题（需要返回匹配列表，以及查找多个匹配）。
类似 Java 的递归函数伪代码可能如下所示：
findMatches(treeNode, searchNode) {
if searchNode has no children {
// search successful
pairs = [] // empty list
return [pairs] // list of lists
}
else {
matches = [] // empty list
searchChild = first child node of searchNode
searchNode2 = searchNode with searchChild removed
// NOTE: searchNode2 is created by doing a shallow copy of just the node
// (not it's children) and then removing searchChild from the child list.
for each treeChild in treeNode.children {
if treeChild.value == searchChild.value {
treeNode2 = treeNode with treeChild removed // also a shallow copy
childMatches = findMatches(searchChild, treeChild)
nodeMatches = findMatches(treeNode2, searchNode2)
// cross-product
for each nodeMatchPairs in nodeMatches {
for each childMatchPairs in childMatches {
fullMatchPairs = [(searchChild, treeChild)]
+ childMatchPairs + nodeMatchPairs // concatenate lists
add fullMatchPairs to matches
}
}
}
}
return matches
}
}
请注意，此函数不会测试 treeNode.value == searchNode.value，或将其添加到列表中。调用者需要这样做。该函数需要在树的每个节点上运行。
按照目前的设计，它可能使用太多内存，但这可以优化。
其他提示
这 可能会有帮助。
