Suchbaumeigenschaft rekursiv programmieren

[jelly]

Hallo Java-Forum,

ich habe versucht, eine Rekursive Methode, die die Suchbaumeigenschaft eines Baumes überprüft, zu programmieren... allerdings funktioniert das nicht so, wie ich möchte, d.h. es wird immer das letzte return-Statement ausgegeben, aber seht selbst:

public boolean check(Node n) {
        if (n == null)
            return false;
        
        if (n.getLeftChild() != null) {
            if (n.getLeftChild().getKey() <= n.getKey()) {
                check(n.getLeftChild());
            } else {
                return false;
            }
        }

        if (n.getRightChild() != null) {
            if (n.getRightChild().getKey() >= n.getKey()) {
                check(n.getRightChild());
            } else {
                return false;
            }
        } 
        return false;
    }

Naja, wenn man ausgaben hinzufügt, sieht man, dass er nur den richtigen Teil des Baumes ausgibt, also kanns daran nicht liegen

 

[SlaterB]

> if (n.getLeftChild().getKey() <= n.getKey()) {
> check(n.getLeftChild());

hier wird check rekursiv aufgerufen, aber dessen Rückgabewert, ob true oder false, wird gänzlich ignoriert,
welcher Sinn hat dieser Aufruf?
soll es vielleicht

if (n.getLeftChild().getKey() <= n.getKey()) {
return check(n.getLeftChild());

lauten?
bei anderen rekursiven Aufrufen genauso

vielleicht auch nur dann true zurückgeben, wenn der rekursive check true ergibt?

--------

> if (n.getLeftChild() != null) {
> if (n.getLeftChild().getKey() <= n.getKey()) {
> check(n.getLeftChild());
> } else {
> return false;
> }
> }

wenn ein linkes Child vorhanden ist, aber der Key nicht passt, wird direkt false zurückgegeben,
muss das rechte Child gar nicht geprüft werden?

 

[jelly]

Danke für Deine Antwort erstmal...

Naja das Problem ist, dass, wenn ich

return check(n.getLeftChild());

mache, dann ist alles was dahinter kommt unreachable... ich hab schon versucht, das über eine boolean-Variable zu regeln, aber das hat noch weniger geklappt ^^

Ja, das Programm soll false zurückgeben, sobald ein Child nicht mehr passt... dann ist ja die Eigenschaft nicht mehr erfüllt...

Sry, dass ich nicht mehr schreiben kann, denn sonst verpass ich meinen Bus. Bis später.

 

[SlaterB]

tja, es gibt verschiedenste Möglichkeiten,

wahrscheinlich habe ich die beiden falschen aufgezählt, weder ein direktes return noch ein return bei true sind richtig,
sondern wenn der rekursive Check false ist, dann auch direkt false zurückgeben, dann ist das 'Ziel' erreicht,

und ganz am Ende der Methode muss dann doch
return true;
stehen, es wurde kein Fehler gefunden