Rekursionsproblem (Bäume)



  • 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.

    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?



  • Implementier doch einfach noch eine interne Methode, die mit einer Liste als Parameter arbeitet.

    Die Methode rufst du dann von der vorgegebenen auf.

    private static List getPathToGoal(ITreeNode root, Object goalNode)
    {
      List list = new ArrayList();
      return getPathToGoalEx(root, goalNode, list);
    }
    

    In getPathToGoalEx schreibst du dann die eigentliche Funktion, die aber eine Liste als Parameter erwartet. D.h. du fügst einfach jedes mal ein Element ein. Dabei bleibt deine Methode sehr kompakt und du verletzt nicht die Vorgaben.



  • Die List nicht immer neu erstellen, sondern als parameter übergeben.



  • ok, damit löse ich das problem mit der liste an sich.

    Mein anderes Problem ist aber, dass ich beim Rekursionsrücklauf nicht mehr den Knoten zum greifen kriegen von dem ich meinen zielknoten erreiche.

    ich schreibe derzeit nur den zielknoten in diese liste und nichts anderes, ich muss halt den weg darein schreiben der zum ziel geführt hat.

    die andere knoten die sich noch ergeben haben, aber nicht auf dem weg zum ziel liegen dürfen sinnvollerweise nicht mit auftauchen. Ich kriege es hin dass alle drin sind oder nur einer (Zielknoten).

    da liegt mein problem. beim rekursionsrücklauf die knoten wegzuschreiben......



  • Je nachdem was für einen Baum du hast, weißt du doch eigentlich schon, welchen Weg du gehen musst.

    In einem Binärbaum bspw. ist der Vergleich zweier Elemente klar definiert, du kannst also mit "<" prüfen, ob du in den linken oder rechten Teilbaum / Knoten gehen musst. Irgendwann bist du am Ziel.

    Oder _musst_ du im Baum alle Knoten, bis du am Zielknoten bist, durchgehen?

    Ansonsten prüfst du alle Knoten und lieferst (wenn ein Knoten keine Söhne mehr hat) null zurück. Wenn das zurückgelieferte Ergebnis null ist, gehst du einfach weiter, ist das Ergebnis ein Knoten, fügst du den ein. Das müsste auch klappen (ungeprüft, evtl. Schwachsinn :P)



  • Ich denk mal so sollte es gehen, habs aber nicht getestet:

    public static List getPathToGoal(ITreeNode root, Object goalNode)
    {           
      if (root.getValue().equals(goalNode))
      {
        List r = new ArrayList();
        r.add(root.getValue().toString());
        return r;
      }
    
      boolean found = false;
      List b; 
    
      for(int i=0; i<root.getChildren().size() && !found; ++i)
      {
        b = getPathToGoal((ITreeNode)it.next(), goalNode);
        if(b != null)
        { 
          b.add(root.getValue().toString());
          found = true;
        }
      }
    
      if(!found)
        return null;
      else
       return b;
    }
    

Log in to reply