spezifische Knoten in einem Baum zählen

[DarylDixon]

Hey Leute,
für meine Klausurvorbereitung bin ich auf eine Aufgabe gestoßen, die mich seit gestern verzweifeln lässt.

Ich soll gewisse Knoten in einem nicht binären Baum zählen. Ich habe es einigermaßen geschafft, bin trotzdem unzufrieden mit meinem Code:

public int countSpecificNodes(String text) {
        if (root != null) {
            return countSpecificNodes(root, text);
        }
        return 0;
    }

    //Aufgabenteil b)
    public int countSpecificNodes(Node node, String bezeichnung) {
    
        if (node.getGemuese().getBezeichnung().equals(bezeichnung)) {
            counter++; //Den Counter habe ich außerhalb der Methode initialisiert
        }
        if (node.getLeft() != null) {

            countSpecificNodes(node.getLeft(), bezeichnung);
        }

         if (node.getRight() != null) {

            countSpecificNodes(node.getRight(), bezeichnung);

        }
        return counter;
    }

Ich habe einen Counter außerhalb der Methode initialisiert, etwas, was ich noch nie so gesehen/getan habe.

Ich würde gerne wissen, wie ich den selben Code ohne Counter schreiben könnte und bräuchte dabei eure Hilfe! 🙂

 

[httpdigest]

[...] in einem nicht binären Baum [...]

public int countSpecificNodes(Node node, String bezeichnung) {
...
  if (node.getLeft() != null) {
    countSpecificNodes(node.getLeft(), bezeichnung);
  }
  if (node.getRight() != null) {
    countSpecificNodes(node.getRight(), bezeichnung);
  }
...
}

sieht ziemlich binär für mich aus, der Baum. Es gibt anscheinend genau (höchstens) zwei Kinder pro Knoten.

Zur Lösungsidee: Überlege doch einmal, wie du den Rückgabewert jedes weiteren rekursiven Aufrufes nutzen kannst.
Kannst du die (Teil-)ergebnisse von countSpecificNodes() für left und right Child vielleicht irgendwie weiter nutzen im Parent?

 

[DarylDixon]

sieht ziemlich binär für mich aus, der Baum. Es gibt anscheinend genau (höchstens) zwei Kinder pro Knoten.

Sorry, ich meine natürlich, dass es sich nicht um einen Suchbaum handelt!

Überlege doch einmal, wie du den Rückgabewert jedes weiteren rekursiven Aufrufes nutzen kannst.

Meinst du, dass ich mit

return countSpecificNodes() + 1;

arbeiten soll?

 

[mihe7]

Du sollst in einem Baum, dessen Wurzelknoten Du erhältst, die Anzahl der Knoten zählen, die eine bestimmte Eigenschaft erfüllen.

Wo kann diese Eigenschaft also auftreten? Klar, im Wurzelknoten selbst. Bis dahin kann die Anzahl also 0 oder 1 sein. Hinzu kommt aber die Anzahl der Knoten, die im linken Teilbaum die Eigenschaft erfüllen. Gleiches gilt natürlich auch für den rechten Teilbaum. Also addieren und fertig.

 

[DarylDixon]

Du sollst in einem Baum, dessen Wurzelknoten Du erhältst, die Anzahl der Knoten zählen, die eine bestimmte Eigenschaft erfüllen.

Wo kann diese Eigenschaft also auftreten? Klar, im Wurzelknoten selbst. Bis dahin kann die Anzahl also 0 oder 1 sein. Hinzu kommt aber die Anzahl der Knoten, die im linken Teilbaum die Eigenschaft erfüllen. Gleiches gilt natürlich auch für den rechten Teilbaum. Also addieren und fertig.

Wie addiere ich denn die Anzahl der Knoten ohne einen linkscounter und einen rechtscounter?

 

[mihe7]

Wie addiere ich denn die Anzahl der Knoten ohne einen linkscounter und einen rechtscounter?

Um mal bei Deinem Code zu bleiben:

    public int countSpecificNodes(Node node, String bezeichnung) {
        int counter = 0;
        if (node.getGemuese().getBezeichnung().equals(bezeichnung)) {
            counter = 1;
        }

        if (node.getLeft() != null) {
            counter += countSpecificNodes(node.getLeft(), bezeichnung);
        }

         if (node.getRight() != null) {
            counter += countSpecificNodes(node.getRight(), bezeichnung);
        }
        return counter;
    }

 

[DarylDixon]

int counter = 0;

Wieso wird counter nicht bei jedem Methodenaufruf wieder auf 0 gesetzt?

 

[fhoffmann]

Wieso wird counter nicht bei jedem Methodenaufruf wieder auf 0 gesetzt?

Jeder Methodenaufruf hat seine eigene Variable counter.

 

[DarylDixon]

Danke für eure Hilfe. Ich bin den Code jetzt mit dem Debugger durchgegangen und kann es einigermaßen nachvollziehen. Rekursionen sind nicht immer einleuchtend :/

 

[mihe7]

Wieso wird counter nicht bei jedem Methodenaufruf wieder auf 0 gesetzt?

Da counter in der Methode deklariert wird, handelt es sich um eine lokale Variable, die nur innerhalb des jeweiligen Methodenaufruf existiert.

Realisiert wird dies dadurch, dass bei einem Methodenaufruf auf dem Stack ein Bereich (sog. stack frame) eingerichtet wird, der unter anderem den Speicherplatz für die lokalen Variablen der Methode enthält.

Beim ersten Aufruf der Methode hast Du also einen Frame #1, in dem Du einen Speicher für die Variable counter findest. Jetzt ruft die Methode sich selbst auf: ein neuer Frame #2 wird eingerichtet, in dem wieder Speicher für die Variable counter zu finden ist usw.

Eine Zuweisung an counter im ersten Aufruf manipuliert also den Speicher in Frame #1, eine Zuweisung im rekursiven Aufruf den Speicher in Frame #2 usw.

Noch was: der Stack ist in seiner Größe begrenzt. Wenn Du eine Endlosrekursion baust, werden so lange neue stack frames eingerichet, bis der Stack voll ist. Danach kommt es zum berühmten "stack overflow", der in Java zu einer StackOverflowException führt.

Rekursionen sind nicht immer einleuchtend :/

Der Witz ist, dass Rekursionen oft so einfach sind, dass man nur zu kompliziert denkt 🙂

Gerade bei rekursiven Datenstrukturen hilft es, in "Element" und "Rest(e)" zu denken: die Methode behandelt nur das Element und ruft sich selbst für den Rest (bzw. die Reste) auf.