ابحث عن جميع الأشجار الفرعية في شجرة مطابقة لشجرة فرعية معينة في جافا

Question

أنا أكتب رمزًا في Java يستخدم شجرة غير مرتبة جذور حيث قد يكون لكل عقدة أي عدد من العقد الفرعية. نظرًا لشجرة T و Tractree S ، أريد أن أكون قادرًا على العثور على جميع الأشكال الفرعية في T التي تتطابق مع S (وهذا هو كل الأشقاء الفرعية في T التي هي متماثلة إلى S).

يكون الشجرة الفرعية من T متماثلة إلى S ، إذا كان يمكن تعيين العقد من S إلى عقد T بطريقة تجعل حواف خريطة S على الحواف في T.

أ السؤال السابق سئل عن كيفية العثور على ما إذا كانت الشجرة تحتوي على شجرة فرعية أخرى ، لكنني أريد أن أكون قادرًا على العثور عليها الكل TROUBTRES في T التي تتطابق S. بالإضافة إلى ذلك ، أريد أن أكون قادرًا على التعيين من كل عقدة في كل مباراة في T إلى العقدة المقابلة في S.

أي عندما يتم العثور على تطابق ، يجب إرجاعها ليس فقط كمؤشر للعقدة في T حيث تكون الشجرة متجذرة تتطابق مع S ، ولكن يجب إرجاع المباراة كشيء مثل قائمة أزواج من المؤشرات على العقد [ (T1 ، S1) ، (T2 ، S2) ، ... (TN ، SN)] بحيث يكون T1 مؤشرًا لعقدة في t التي تقوم بتعيين العقدة S1 في الشجرة الفرعية وما إلى ذلك.

بدلاً من ذلك ، يمكن إرجاع قائمة من الأزواج من القيم لأن كل عقدة في TREE T و TRUTREE S لها معرف عدد صحيح فريد مرتبط به.

علي سبيل المثال:

تم إعطاء شجرة T على النحو التالي:

    a
   / \
  b   c
 / \  
d   e

و Sub Treats S as:

    x
   / \
  y   z

يجب إرجاع القائمة التالية للمباريات:

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

يتم تحديد تطابق فريد من خلال مجموعة العقد في T ، ليس التعيين بين العقد في T و S.

لذلك المباراة التالية:

(أ ، س) ، (ب ،ض) ، (ج ،ذ)]

يعتبر مكررة من

(أ ، س) ، (ب ،ذ) ، (ج ،ض)]

لأن لديهم نفس مجموعة العقد من T (A ، B ، C) لذلك يجب إرجاع واحد فقط من المباريات.

كمثال آخر ، تم إعطاء شجرة T:

    a
   /|\
  b c d

و Sub Trave S:

  x
 / \  
y   z

يجب إرجاع القائمة التالية للمباريات:

(a ، x) ، (b ، y) ، (c ، z)] [(a ، x) ، (b ، y) ، (d ، z)] [(a ، x) ، (c ، y) ، (D ، Z)

هل يمكن لأي شخص إعطاء أي رمز مثال على كيفية القيام بذلك؟

تحرير (فيما يتعلق بتعليق كريس كانون):

أعتقد أنك تريد أن يقوم شخص ما بترميز الإجابة لك؟ إلى أي مدى وصلت؟ ما الرمز الذي كتبته؟ - كريس كانون منذ ساعة واحدة

لدي الرمز التالي الذي عند التشغيل ، يقوم بإنشاء قائمة (قائمة مباريات) من المؤشرات إلى العقد في الشجرة حيث يتم تجذير الأشجار الفرعية التي تتطابق مع الشجرة الفرعية المعطاة. ومع ذلك ، قد يكون هناك عدة مجموعات فرعية متجذرة في نفس العقدة ، وفي الوقت الحالي ستتم إضافة كل عقدة فقط مرة واحدة على الأكثر مرة واحدة إلى قائمة المباريات بغض النظر عن عدد المباريات المتجذرة هناك.

بالإضافة إلى ذلك ، لا يمكنني معرفة كيفية بناء التعيين الموضح أعلاه بين العقد في الشجرة الفرعية والعقد في المباراة الموجودة في الشجرة الأصلية.

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 مباريات متأصلة في العقدة العلوية ، وليس فقط. بالإضافة إلى ذلك ، لا يقوم الرمز ببناء رسم خرائط بين العقد في الشجرة والعقد في الشجرة الفرعية ولا يمكنني معرفة كيفية القيام بذلك.

هل يمكن لأي شخص تقديم أي نصيحة حول كيفية القيام بذلك؟

Answer 1

أعتقد أن طريقتك العودية تحتاج إلى إرجاع قائمة من المباريات الجزئية ، بدلاً من مجرد منطقية. من شأن ذلك أن يقطع شوطًا طويلاً في حل مشكلتك (الحاجة إلى إعادة قائمة المباريات ، بالإضافة إلى العثور على مباريات متعددة).

قد يبدو رمز كاذب يشبه Java للوظيفة العودية شيئًا من هذا القبيل:

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

لاحظ أن هذه الوظيفة لا تختبر treeNode.value == searchnode.value ، أو إضافة هذا إلى القائمة. يحتاج المتصل إلى القيام بذلك. يجب تشغيل هذه الوظيفة في كل عقدة من الشجرة.

كما هو مصمم حاليًا ، ربما يستخدم الكثير من الذاكرة ، ولكن يمكن تحسين ذلك.

Answer 2

هذه يمكن أن تكون مفيدة.