Alle Teilbäume in einem Baum einen bestimmten Teilbaum in Java passend

Question

Ich schreibe Code in Java, die einen ungeordneten, Wurzelbaum verwendet, wobei jeder Knoten eines beliebige Anzahl von untergeordneten Knoten hat. Bei einem gegebenen Baum T und ein Teilbaum S, ich möchte, dass alle Teilbäume in T finden können, dass Spiel S (die alle die Teilbäume in T ist, die isomorph S sind).

Ein Teilbaum von T isomorph zu S, wenn die Knoten von S können auf Knoten von T so abgebildet werden, dass die Kanten der S Karte an den Kanten in T.

vorherige Frage wurde gebeten, wie man finden, wenn ein Baum enthält eine weitere Teilstruktur jedoch ich in der Lage sein zu finden, Unterbäume in T das Spiel S. Außerdem möchte ich von jedem Knoten in jedem Spiel in T an die entsprechende Karte in der Lage sein Knoten in S.

Das heißt, wenn eine Übereinstimmung gefunden wird, soll es nicht einfach als ein Zeiger auf den Knoten in T zurückgegeben werden, wo ein Baum, dass Streichhölzer S verwurzelt ist, aber das Spiel sollte so etwas wie eine Liste von Paaren von Zeigern zurückgegeben werden in den Knoten [(T1, S1), (T2, S2), ... (Tn, Sn)], so dass T1 ist ein Zeiger auf einen Knoten in T, dass die Karten an dem Knoten S1 in der Teilstruktur und so weiter.

Alternativ einfach eine Liste von Paaren von Werten als jeden Knoten im Baum T zurückgeführt werden kann, und Teilbaum S hat eine eindeutige ganzzahlige Kennung, die mit ihr verbunden ist.

Zum Beispiel:

Da Baum T wie folgt:

    a
   / \
  b   c
 / \  
d   e

und Teilbaum S wie:

    x
   / \
  y   z

Die folgende Liste von Übereinstimmungen zurückgegeben werden sollte:

  

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

Eine eindeutige Übereinstimmung mit dem Satz von Knoten in T bestimmt wird, nicht die Abbildung zwischen den Knoten in T und S.

So folgendes Spiel:

  

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

gilt als Duplikat

  

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

, weil sie den gleichen Satz von Knoten von T haben (a, b, c), so dass nur eine der Streichhölzer sollten zurückgegeben werden.

Als ein weiteres Beispiel gegeben Baum T:

    a
   /|\
  b c d

und Teilbaum S:

  x
 / \  
y   z

Die folgende Liste von Übereinstimmungen zurückgegeben werden sollte:

  

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

geben kann jemand einem Beispiel-Code, wie dies zu tun?

Edit (in Bezug auf Chris Kannon Kommentar):

  

Ich denke, Sie jemanden Code wollen   die Antwort für Sie? Wie weit Sie haben   bekommen? Was Code haben Sie geschrieben? -   Chris Kannon vor 1 Stunde

Ich habe den folgenden Code, die, wenn sie ausgeführt werden, eine Liste (matchesList) von Zeigern auf Knoten im Baum aufbaut, wo Teilbäume verwurzelt sind, dass erfüllen die Unterstruktur. Jedoch kann es mehr Unterstrukturen auf demselben Knoten verwurzelt sein und zur Zeit wird jeder Knoten nur höchstens einmal zu matchesList hinzugefügt werden, unabhängig davon, wie viele Spiele sind verwurzelt dort.

Darüber hinaus kann ich nicht herausfinden, wie die Abbildung zum Aufbau oben beschrieben zwischen den Knoten im Unterbaum und Knoten im Spiel in dem ursprünglichen Baum gefunden.

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

Der obige Code versucht, alle Subgraphen in finden:

  A
 /|\  
A A A
   / \
  A   A

das Spiel:

    A
   / \
  A   A

Der Code erkennt erfolgreich, dass es eine Übereinstimmung eine der Top-Knoten in der ersten Baum und das dritte Kind des ersten Baums verwurzelt ist. Allerdings gibt es tatsächlich drei Spiele in den oberen Knoten wurzelt, nicht nur eine. Darüber hinaus wird der Code nicht eine Zuordnung zwischen Knoten im Baum und Knoten in der Teilstruktur aufzubauen, und ich kann nicht arbeiten, wie dies zu tun.

Kann jemand bietet einen Rat, wie dies zu tun?

Answer 1

Ich denke, Ihre rekursive Methode benötigt eine Liste von teilweise Übereinstimmungen zurück, anstatt nur einen boolean. Das würde einen langen Weg, beide um Ihre Probleme zu lösen (die Notwendigkeit, die Liste der Spiele, sowie die Suche mehr Treffer zurück).

Java-like Pseudo-Code für die rekursive Funktion könnte wie folgt aussehen:

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
    }
}

Beachten Sie, dass diese Funktion testet nicht treeNode.value == searchNode.value, oder diese in die Liste aufzunehmen. Der Anrufer muss das tun. Diese Funktion benötigt an jedem Knoten des Baumes ausgeführt werden.

Wie zur Zeit entwickelt, ist es wahrscheinlich zu viel Speicher verwendet, aber das optimiert werden kann.

Answer 2

Diese kann hilfreich sein.