我正在用 Java 编写代码，该代码使用无序的有根树，其中每个节点可能有任意数量的子节点。给定一棵树 T 和一个子树 S，我希望能够找到 T 中与 S 匹配的所有子树（即 T 中与 S 同构的所有子树）。
如果 S 的节点可以映射到 T 的节点，使得 S 的边映射到 T 中的边，则 T 的子树与 S 同构。
上一个问题已被问及如何查找树是否包含另一个子树，但是我希望能够在 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,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 个匹配根植于顶部节点，而不仅仅是一个。此外，代码没有在树中的节点和子树中的节点之间建立映射，我无法弄清楚如何做到这一点。
任何人都可以就如何做到这一点提供任何建议吗？