Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
20.06.2008, 16:51 Uhr
~Justi
Gast

hallo,

hab hier ein Rekursionsproblem was ich zum verrecken nicht gelöst kriege.

Die Methode um die es gibt gehört zu einem Algorithmus um Bäume zu durchsuchen. Die Methode soll mir in einer List den Weg vom Startknoten zum Zielknoten ausgeben.

Das hab ich natürlich über Rekursion gelöst. Aber ich schaffe es nicht es vom Konzept her so zu verbasteln, dass er mir beim Rekursionsrücklauf alle Knotennamen in meine Liste schreibt.

Bis auf den Knoten, der mein Ziel darstellt landet keiner meiner Knoten in der Liste, das Problem kann ich zwar sehen und verstehen, aber ich weis niht wieich das lösen soll.

C++:

    public static List getPathToGoal(ITreeNode root, Object goalNode)
        {
            List i = new ArrayList();

            if (root.getValue().equals(goalNode))
            {
                List r = new ArrayList();
                r.add(root.getValue().toString());
                return r;
            }

            Iterator it = root.getChildren().iterator(); //Root kann mehrere Kinder haben

            while (it.hasNext())
            {

                /** Zurückgelieferte Liste empfangen und Elemente daraus in Rückgabeliste übertragen */
                List b;
                b = getPathToGoal((ITreeNode) it.next(), goalNode);
                Iterator bt = b.iterator();

                while (bt.hasNext()) //temporäre Liste in return-liste übertragen
                {
                    i.add(bt.next());
                }
            }

            return i;

         }

Mir ist es aber verboten etwas and er methoden definition zu ändern, da ich das aus schulisch mache und deswegen vorgaben hab.

Das Prinzip der Rekursion hab ich verstanden, aber ich kann das einfach nicht richtig hier drauf anwenden.

Kann mir jemand helfen?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
20.06.2008, 18:47 Uhr
kronos
Quotenfisch
(Operator)

Sehe an sich keinen Fehler. Mach doch mal ein paar Ausgaben 'rein, um zu sehen durch welch Knoten er tatsächlich läuft, wann welche List was enthält etc.
--
main($)??<-$<='?'>>2?main($-!!putchar(
(("$;99M?GD??(??/x0d??/a:???;a"+'?'/4)
??($??)+'?'/3-2-1+$%2)??''?')):'?';??>

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
22.06.2008, 11:59 Uhr
~B.Nutzer
Gast

Du rufst getPathToGoal zwar rekrusiv auf, uebernimmst dessen Rueckgabewert aber "blind". Zudem fuegst du "root", also das aktuelle Element, nur dann in die Liste ein, wenn es das Ziel ist. Das fuehrt dazu das getPathToGoal immer nur das Ziel-Objekt zurueckgibt.

Mein Code wuerde etwa so aussehen.
(Wichtig: Ich habe den Code weder getestet noch bewiesen das er funktioniert ;-) )

C++:

public static List<Object> getPathToGoal(ITreeNode root, Object goalNode) {
    LinkedList<Object> i = new LinkedList<Object>();

    if(root.getValue().equals(goalNode)) {
        i.add(root.getValue().toString());
        return i;
    }

    Iterator<ITreeNode> it = root.getChildren().iterator();
    while (it.hasNext()) {
        List<Object> path = getPathToGoal((ITreeNode) it.next(), goalNode);
        if(path != null) { // ist path der "richtige" Weg?
            i.add(root.getValue().toString());
            i.addAll(path);
            return path;
        }
    }
    return null; // Dieser Weg fuehrt nicht zum Ziel.
}

P.S: Du kannst natuerlich List<Object>, Iterator<ITreeNode>, etc. durch List, Iterator und Co. ersetzen, solltest du das wollen oder gar muessen (falls du z.B. noch Java < 1.5 verwendest oder ITreeNode nicht anpassen darfst).

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ Java ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: