Binärbaum rekursiv durchsuchen und Referenz zurückgeben

[affot]

Hallo zusammen,

ich habe noch Probleme mit der Anwendung von rekursiven Methoden und versuche es mit üben üben üben.
Darum knobel jetzt seit über einer Stunde an meiner mir selbst erlegten Aufgabe rum aber komme einfach nicht auf eine funktionierende Lösung.
Ich möchte einen Binärbaum (Knoten mit int-Werten) durchlaufen und nach einem bestimmten Wert suchen.
Den Baum mit einer void-Methode durchlaufen und sagen auf welcher Ebene sich der Wert befindet (sofern vorhanden) ist kein Problem:
Der main() Aufruft erfolgt mit findRekursiv(baum.wurzel, 'gesuchter Wert',1) mit Start auf Ebene 1.

    void findRekursiv(Knoten knoten, int wert, int ebene) {
        if (knoten != null) {
            if (knoten.getWert() == wert) {
                System.out.println("Gefunden auf Ebene " + ebene + ".");
            } else {
                findRekursiv(knoten.links, wert, ebene + 1);
                findRekursiv(knoten.rechts, wert, ebene + 1);
            }
        }
    }

Problematisch ist nur hier: Wenn der Wert NICHT vorkommt, wie kann ich das anzeigen? Also ohne bei jedem Aufruf zu sagen "hier nicht gefunden".

Und viel brennender ist für mich die Frage (die in die selbe Richtung geht, denn eine Information muss ja irgendwie durchgereicht werden):
Wie mache ich es, wenn ich gleichzeitg noch eine Referenz auf dieses Element zurückgeben möchte (sofern vorhanden)?

Ich habe schon zig Varianten ausprobiert und poste hier einfach mal meine letzte Version. Es funktioniert insofern, dass ich beim Element ankomme und das in der Console ausgebe. Aber die Referenz wird halt nicht weitergereicht. Ich denke sie wird einmal weitergereicht nur da ich im Rekursionsschritt vorher ja einmal "falsch" abgebogen bin wird aus diesem Weg null weitergereicht, was dann ganz am Ende ankommt.
Also salopp gesagt möchte ich sowas realisieren wie: "Wenn du irgendwo auf deinem Weg mal einen richtigen Knoten erhalten hast dann reiche auf jeden Fall diesen weiter, ansonsten null - aber bevorzuge immer den Knoten".
Aber irgendwie will mir das nicht gelingen.

   Knoten findRekursiv1(Knoten knoten, int wert, int ebene) {
          if (knoten != null) {
            if (knoten.getWert() == wert) {
                System.out.println("Gefunden auf Ebene " + ebene + ".");
                return knoten;
            } else {
                findRekursiv1(knoten.links, wert, ebene + 1);
                findRekursiv1(knoten.rechts, wert, ebene + 1);
                return null;
            }
        } else {
            return null;
        }
    }

 

[LimDul]

Der Code sieht schon mal nicht schlecht aus.

Nur dein else zweig mit den rekursiven Aufrufen passt noch nicht ganz. Die findeRekursiv Aufrufe geben ja einen Wert zurück. Den musst du auswerten und ggf. nach oben durchreichen. Deine Methode hat ja die Semantik:
* Ein Wert ungleich null => Knoten wurde gefunden
* Ein Wert gleich null => Knoten wurde nicht gefunden.

Damit sehe das wie folgt aus:

   Knoten findRekursiv1(Knoten knoten, int wert, int ebene) {
          if (knoten != null) {
            if (knoten.getWert() == wert) {
                System.out.println("Gefunden auf Ebene " + ebene + ".");
                return knoten;
            } else {
                Knoten links = findRekursiv1(knoten.links, wert, ebene + 1);
                Knoten rechts = findRekursiv1(knoten.rechts, wert, ebene + 1);
                if (links != null) {
                    return links;
                } else {
                    return rechts;
                }
            }
        } else {
            return null;
        }
    }

 

[affot]

Oh Mann, ich hatte schon alles mit return findRekursiv(...) in if-else Bedingunendurchprobiert, aber auf die links/rechts Idee bin ich nicht gekommen...
Vielen Dank für deine Lösung!

Mein Problem bei den Rekursionen ist einfach noch: Wenn ich sie sehe dann verstehe ich sie, aber selbst drauf kommen gelingt mir noch wirklich häufig nicht... Fällt da irgendwann automatisch der groschen oder gibt es da einen geeigneten Weg wie man es sich methodisch beibringt, so dass man es dann auch selbst anwenden kann?

 

[LimDul]

Oft muss man das ein paar mal machen bis man da fitter wird - bei dem einen geht es schneller, beim anderen dauert es länger.

Was helfen kann ist sich komplett vom Code zu lösen und es mal in Prosa zu formulieren.

* Entweder ist der aktuelle Knoten der gesuchte => Gib ihn zurück
* Wenn es nicht der gesuchte ist, schaue links & rechts ob es da der gesuchte Knoten da ist und liefere den zurück.


Und wenn man das dann versucht umzusetzen, kommt man hoffentlich auf eine Lösung ähnlich wie die oben.

 

[affot]

Ok, dann werde ich es die nächsten Male mal mit dem Ansatz versuchen wenn ich hänge.
Danke! 🙂