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.
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.
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.
Code:
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.
Code:
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;
}
}