Binäre Bäume Rekursiv durchlaufen und bestimmte Elemente Zählen

[Cassy3]

Hey Leute, ich habe wieder ein Wunderschönes Anfängerproblem und hoffe, ihr könnt mir helfen.
Ich habe einen Binären Suchbaum. Durch diesen soll ich Rekursiv durch gehen und zählen, wie viele meiner Mitarbeiter älter sind als das übergebene Jahr.

Mein Code sieht so aus:

    public int filter (int year) {
        if (root ==null) {
            return 0;
        }
        else {
            return filter(0, year, root);
        }
    }
    
    public int filter (int count, int geburtsjahr, EmployeeTreeNode currentNode) {
        
            if (currentNode.getEmployee().getYearOfBirth()<geburtsjahr) {
                count++;
                System.out.println(currentNode.getEmployee().getYearOfBirth());
                System.out.println(count);
            }
            
            if (currentNode.getLeftSuccessor()!=null) {
                filter (count, geburtsjahr,currentNode.getLeftSuccessor());
            }
            
            if (currentNode.getRightSuccessor()!=null) {
                filter(count, geburtsjahr,currentNode.getRightSuccessor());
            }
                
        return count;
    }

Meine Ausgabe dann so:

1900
1
1901
2
Anzahl an Mitarbeitern die Älter sind als vom Jahre 2010: 0

Ich verstehe das nun wirklich nicht. Könnte mir irgendwer erklären, warum das Count in der if übernommen wird und dann unten in der Return scheinbar die Inkrementation komplett ignoriert? Ich danke schonmal für jede Hilfe

 

[mihe7]

Könnte mir irgendwer erklären, warum das Count in der if übernommen wird und dann unten in der Return scheinbar die Inkrementation komplett ignoriert?

Naja, Du verwendest den Rückgabewert ja nirgends. Zum Beispiel rufst Du in Zeile 19 zwar filter auf und die Methode gibt einen Wert zurück aber Du machst mit dem Wert nix.

 

[Cassy3]

Naja, Du verwendest den Rückgabewert ja nirgends. Zum Beispiel rufst Du in Zeile 19 zwar filter auf und die Methode gibt einen Wert zurück aber Du machst mit dem Wert nix.

Könntest du mir das nochmal genauer Erklären? Weil in Zeile 19 und 23 soll ja auch an sich nicht viel gemacht werden, da da ja nur weiter im baum Spaziert werden soll und dann, wenn er wieder an einem Anderen Knoten ist erneut überprüfen, ob der Mitarbeiter älter ist. Er zählt das alles ja auch vernünftig. Siehe Ausgabe 1,2 (erste If)
Aber wenn es dann darum geht, diese Zahl auszugeben, funktioniert nichts. Verstehst du, wie ich das meine und wo wahrscheinlich mein Denkfehler liegt?

 

[mihe7]

Dein Denkfehler liegt darin, zu glauben, dass "count" nur einmal existiert. Tatsächlich existiert count für jeden Methodenaufruf separat.

 

[Cassy3]

Danke, ich habe den Fehler gefunden, so funktioniert es.

    public int filter (int count, int geburtsjahr, EmployeeTreeNode currentNode) {
        
        
            if (currentNode.getEmployee().getYearOfBirth()<geburtsjahr) {
                count++;
            }
            
            if (currentNode.getLeftSuccessor()!=null) {
                count=filter (count, geburtsjahr,currentNode.getLeftSuccessor());
            }
            
            if (currentNode.getRightSuccessor()!=null) {
                count=filter(count, geburtsjahr,currentNode.getRightSuccessor());
            }
                
        return count;
    }

Jedoch wäre ich dankbar, wenn du mir erklären könntest, wieso es so ist, dass count mehrere Male existiert

 

[mihe7]

Für den Methodenaufruf wird ein Speicherbereich auf dem Stack eingerichtet, der sog. Stackframe. In dem finden sich neben Platz für die lokalen Variablen auch die Rücksprungadresse (der Rechner muss ja wissen, an welche Stelle man zurückkehren muss) und die übergebenen Parameter. Wenn die Methode zurückkehrt, wird der Stackframe vom Stapel genommen.

 

[mihe7]

BTW: Das ist auch der Grund, warum es bei einer Endlosrekursion zu einem "stack overflow" kommt