Найдите все поддеревья в дереве, соответствующем данному поддереву в Java

Я - написание кода в Java, который использует незаказанный, базировался дерево, где каждый узел может иметь любое количество дочерних узлов. Учитывая дерево T и поддерево S, я хочу смочь найти все поддеревья в T, которые соответствуют S (который является всеми поддеревьями в T, которые изоморфны к S).

Поддерево T изоморфно к S, если узлы S могут быть отображены на узлах T таким способом, которым края S отображаются на края в T.

Предыдущий вопрос задали о том, как найти, содержит ли дерево другое поддерево однако, я хочу смочь найти ВСЕ поддеревья в 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):

Я думаю, что Вы хотите, чтобы кто-то кодировал ответ для Вас? Как далеко Вы добрались? Какой код Вы написали? – 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 matchesList = new LinkedList();

    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 children;

    public NodeX(char val) {
        value = val;
        children = new Vector();
    }

    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-м ребенке первого дерева. Однако существует на самом деле 3 соответствия, базированные в главном узле, не всего один. Кроме того, код не создает отображение между узлами в дереве и узлами в поддереве, и я не могу разработать, как сделать это.

Кто-либо может дать совет о том, как сделать это?