Я пишу код на Java, который использует неупорядоченное корневое дерево, где каждый node может иметь любое количество дочерних узлов. Учитывая дерево T и поддерево S, я хочу, чтобы найти все поддеревья в T, которые соответствуют S (это все поддеревья в T, которые изоморфны S).
Поддерево T изоморфно S, если узлы S могут быть отображены в узлы T таким образом, чтобы ребра S отображались на ребра в T.
A предыдущий вопрос был задан вопрос о том, как найти дерево в другом поддереве, но я хочу найти подделки ВСЕ в T, которые соответствуют S. Кроме того, я хочу иметь возможность отображать из каждого node в каждом совпадении в T с соответствующим node в S.
То есть, когда совпадение найдено, оно должно быть возвращено не просто как указатель на node в T, где дерево коренится, которое соответствует S, но совпадение должно быть возвращено как что-то вроде списка пар указателей на узлы [(T1, S1), (T2, S2),... (Tn, Sn)] такие, что T1 является указателем на node в T, который отображается в node S1 в поддереве и скоро.
Альтернативно просто список пар значений может быть возвращен как каждый node в дереве T, а поддерево S имеет уникальный идентификатор целого числа, связанный с ним.
Например:
Указанное дерево T следующим образом:
a
/ \
b c
/ \
d e
и поддерево S как:
x
/ \
y z
должен быть возвращен следующий список совпадений:
[(а, х), (б, г), (с, г)] [(Ь, х), (д, у), (е, г)]
Уникальное совпадение определяется набором узлов в T, not отображением между узлами в T и S.
Итак, следующее совпадение:
[(а, х), (Ь, <Ь > г), (С, у)]
считается дубликатом
[(а, х), (б, у), (с, г)]
потому что они имеют одинаковый набор узлов из T (a, b, c), поэтому нужно возвращать только одно из совпадений.
В качестве другого примера, данное дерево T:
a
/|\
b c d
и поддерево S:
x
/ \
y z
должен быть возвращен следующий список совпадений:
[(а, х), (б, г), (с, г)] [(А, х), (б, г), (д, г)] [(А, х), (с, у), (д, г)]
Может ли кто-нибудь дать какой-нибудь пример кода, как это сделать?
Изменить (по отношению к комментарию Криса Кэннона):
Я думаю, вы хотите, чтобы кто-то закодировал ответ для вас? Как далеко вы получили? Какой код вы написали? - Крис Кэннон 1 час назад
У меня есть следующий код, который при запуске создает список (matchList) указателей на узлы в дереве, где корни основаны на корнях, которые соответствуют данному поддереву. Однако может быть несколько поддеревьев, внедренных в один и тот же node, и в настоящее время каждый node будет добавлен не более одного раза в matchList, независимо от того, сколько совпадений коренится там.
Кроме того, я не могу решить, как создать описанное выше сопоставление между узлами в поддереве и узлах в совпадении, найденном в исходном дереве.
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
Код успешно обнаруживает, что существует совпадение, связанное с верхним node в первом дереве и третьим дочерним элементом первого дерева. Тем не менее, на самом деле есть 3 матча, основанных на вершине node, а не только на одном. Кроме того, код не создает сопоставление между узлами в дереве и узлами в поддереве, и я не могу понять, как это сделать.
Может кто-нибудь предложить какие-либо советы о том, как это сделать?
