Finden Sie alle Teilbäume in einem Baum, die mit einem bestimmten Teilbaum in Java

Schreibe ich code in Java verwendet eine ungeordnete, verwurzelter Baum, wo jeder Knoten kann eine beliebige Anzahl von Kind-Knoten. Gegeben ein Baum T und ein Teilbaum S, ich möchte in der Lage sein, um herauszufinden, alle Teilbäume in T, match S (das ist alles, die Teilbäume in T sind isomorph zu S).

Einen Teilbaum von T ist isomorph zu S, wenn die Knoten von S zugeordnet sein kann, die Knoten von T so, dass die Kanten von S-Karte, um die Kanten in T.

Einen Vorherige Frage wurde gefragt, wie Sie zu finden, wenn ein Baum enthält eine weitere Unterstruktur aber ich möchte in der Lage zu finden ALLE Teilbäume in T entsprechen S. außerdem will ich in der Lage sein, aus der die Zuordnung jeder Knoten in jedem match in T, um die entsprechenden Knoten in S.

Ist, wenn eine übereinstimmung gefunden wird, sollte es zurückgegeben werden und nicht einfach ein Zeiger auf den Knoten in T, wo ein Baum verwurzelt ist, entspricht S, aber das match sollte zurückgegeben werden, wie so etwas wie eine Liste von Paaren von Zeigern auf Knoten [(T1,S1),(T2,S2),...(Tn,Sn)], so dass T1 ist ein Zeiger auf einen Knoten in T, die Karten auf Knoten S1 im Teilbaum und so weiter.

Alternativ einfach eine Liste von Paaren von Werten zurückgegeben werden, da jeder Knoten im Baum T und Teilbaum von S hat eine eindeutige integer-id zugeordnet.

Beispiel:

Gegebenen Baum T wie folgt:

    a
   / \
  b   c
 / \  
d   e

und Teilbaum S:

    x
   / \
  y   z

folgenden die Liste der Spiele, die zurückgegeben werden sollen:

[(a,x),(b,y),(c,z)]
[(b,x),(d,y),(e,z)]

Einem einzigartigen match wird bestimmt durch die Menge der Knoten in T, nicht das mapping zwischen den Knoten in T und S.

Also das folgende match:

[(a,x),(b,z),(c,y)]

als Duplikat

[(a,x),(b,y),(c,z)]

da Sie die gleiche Menge von Knoten aus T (a,b,c), so dass nur eines der Spiele, die zurückgegeben werden sollen.

Als ein weiteres Beispiel, da der Baum T:

    a
   /|\
  b c d

und Teilbaum S:

  x
 / \  
y   z

folgenden die Liste der Spiele, die zurückgegeben werden sollen:

[(a,x),(b,y),(c,z)]
[(a,x),(b,y),(d,z)]
[(a,x),(c,y),(d,z)]

Kann jemand geben Sie ein beliebiges Beispiel-code, wie dies zu tun?

Bearbeiten (in Bezug auf Chris Kannon ' s Kommentar):

Ich denke, Sie möchten, dass jemand den code
die Antwort für Sie? Wie weit haben Sie
bekommen? Welchen code hast du geschrieben? –
Chris Kannon vor 1 Stunde

Ich habe den folgenden code, die, wenn Sie ausgeführt wird, erzeugt eine Liste (matchesList) von Zeigern auf Knoten in dem Baum, in dem Teilbaum verwurzelt sind, dass entsprechend der gegebenen Teilstruktur. Allerdings kann es mehrere Teilbäume verwurzelt in der gleichen Knoten-und derzeit jeder Knoten wird nur dann Hinzugefügt werden, höchstens einmal zu matchesList unabhängig davon, wie viele Spiele sind dort verwurzelt.

Zudem kann ich nicht arbeiten heraus, wie man die Zuordnung oben beschrieben zwischen den Knoten im Teilbaum und Knoten in das match gefunden in den ursprünglichen Baum.

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();
    }
}

Den code oben versucht zu finden, die alle Teilgraphen in:

  A
 /|\  
A A A
   / \
  A   A

dem match:

    A
   / \
  A   A

Den code erfolgreich erkannt wird, dass es eine übereinstimmung wurzelt eine der top-Knoten im ersten Baum, und das 3. Kind der erste Baum. Allerdings gibt es tatsächlich 3 Spiele verwurzelt in der top-Knoten, nicht nur eine. Darüber hinaus wird der code nicht aufbauen, ein mapping zwischen den Knoten in der Baumstruktur und Knoten in dem Teilbaum, und ich kann nicht herausfinden, wie dies zu tun.

Kann mir jemand einen Rat, wie dies zu tun?