spezifische Knoten in einem Baum zählen

DarylDixon

Mitglied
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:

Java:
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

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

Java:
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

Mitglied
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
Java:
return countSpecificNodes() + 1;
arbeiten soll?
 

mihe7

Top Contributor
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

Mitglied
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

Top Contributor
Wie addiere ich denn die Anzahl der Knoten ohne einen linkscounter und einen rechtscounter?
Um mal bei Deinem Code zu bleiben:
Java:
    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

Mitglied
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

Top Contributor
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
G Teil(e) eines Strings entfernen wenn spezifische Zeichen (< & >) vorkommen Java Basics - Anfänger-Themen 5
H Suche spezifische Eigenschaft von Object - sowas wie ".hashCode()" Java Basics - Anfänger-Themen 4
R JNI: (WIN)API-spezifische Parameter mappen? Java Basics - Anfänger-Themen 2
H Liste Knoten NullPointerException Java Basics - Anfänger-Themen 7
Cassy3 Binärer Suchbaum Knoten rauslöschen Java Basics - Anfänger-Themen 1
Y Knoten an einem gegebenen Index aus einer Liste entfernen. Java Basics - Anfänger-Themen 6
Y Wie greift man auf die Knoten in einem Binärbaum zu? Java Basics - Anfänger-Themen 5
J ActionListener von JCheckBox im Knoten von JTree funktioniert nicht Java Basics - Anfänger-Themen 2
S Binärbäume knoten zählen Java Basics - Anfänger-Themen 16
T Collections Methode (Knoten hinzufügen) für Graphen Java Basics - Anfänger-Themen 32
H Knoten-Reihenfolge einer LinkedList invertieren Java Basics - Anfänger-Themen 11
G Binärer Suchbaum Knoten zählen Java Basics - Anfänger-Themen 1
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
O Suchbaum Elternknoten finden Level eines Knoten bestimmen Java Basics - Anfänger-Themen 24
O Knoten und Liste verarbeitung Java Basics - Anfänger-Themen 20
E Knoten eines Baumes unter Bedinung zählen Java Basics - Anfänger-Themen 2
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
L Baum Knoten zählen Java Basics - Anfänger-Themen 6
L B+Baum innere Knoten erstellen Java Basics - Anfänger-Themen 3
L Graphen: Anzahl Knoten // Knoten in Array speichern Java Basics - Anfänger-Themen 4
I Erste Schritte Referenz zum Knoten davor, in einer Liste Java Basics - Anfänger-Themen 4
J Max. Anzahl von Knoten im Binärbaum Java Basics - Anfänger-Themen 3
M Werte der Knoten in Binärbaum addieren (iterativ) Java Basics - Anfänger-Themen 6
S Baumstruktur: tiefsten Knoten finden Java Basics - Anfänger-Themen 3
B Methoden BinärBaum als String Knoten löschen Java Basics - Anfänger-Themen 5
J Baum Knoten löschen Java Basics - Anfänger-Themen 10
T Datentypen Knoten Großvater finden? Java Basics - Anfänger-Themen 12
S Methoden Abtrennen ab einem gegebenen Knoten eines Binärbaums Java Basics - Anfänger-Themen 4
M Binärbaum - Problem bei Knoten anhängen / löschen Java Basics - Anfänger-Themen 5
B JTree knoten wird nicht übernommen Java Basics - Anfänger-Themen 4
L BinärTree, Knoten löschen Java Basics - Anfänger-Themen 6
Luk10 Anzahl der Knoten in einem Baum ausgeben! Java Basics - Anfänger-Themen 6
T gebe mir den ersten eltern knoten Java Basics - Anfänger-Themen 3
K verkettete Listen - Klasse Knoten Java Basics - Anfänger-Themen 19
L LinkedList vorgänger Knoten zurück geben Java Basics - Anfänger-Themen 4
H B-Baum: Knoten Position als Parameter oder als Variable im Objekt? Java Basics - Anfänger-Themen 4
D An bestimmten Knoten einer Liste zugreifen Java Basics - Anfänger-Themen 4
S Binärbaum - Klasse Knoten - Methode Suchen Java Basics - Anfänger-Themen 5
M Nachbar von Knoten bestimmen Java Basics - Anfänger-Themen 8
0x7F800000 zwei adjazenzlisten für jeden knoten eines graphen sinnvoll? Java Basics - Anfänger-Themen 17
C Bäume in Java. Knoten in Array speichern Java Basics - Anfänger-Themen 3
G eine Knoten aus einem Baum löschen. [SOLVED] Java Basics - Anfänger-Themen 7
F JTree-Knoten (DefaultMutableTreeNode) formatieren ? Java Basics - Anfänger-Themen 3
Y JTree: ein Knoten als Objekt Java Basics - Anfänger-Themen 2
K Mehrere Werte in einem Switch Case parallel überprüfen Java Basics - Anfänger-Themen 7
Zrebna Fragen zu einem Klassendiagramm Java Basics - Anfänger-Themen 8
S HashMap mehrere Keys zu einem Value Java Basics - Anfänger-Themen 3
S Java: Wie sortiere ich eine ArrayList benutzerdefinierter Objekte nach einem bestimmten Attribut? Java Basics - Anfänger-Themen 2
F 2x 16bit Werte zu einem 32bit und dann splitten mit 0xb Java Basics - Anfänger-Themen 1
J JSON mit einem JPanel Java Basics - Anfänger-Themen 3
F Einem GIT repository ein Projekt hinzufügen Java Basics - Anfänger-Themen 1
J Frage zu einem "Taschenrechner" code Java Basics - Anfänger-Themen 9
I Klassen von einem package laden, Statisches Feld auslesen und Objekt erstellen Java Basics - Anfänger-Themen 8
J Schlüsselworte Prüfen, ob ein bestimmtes, ganzes Wort in einem String enthalten ist. Java Basics - Anfänger-Themen 6
P Probleme mit NetBeans: Wie lässt sich jar. Datei an einem MacBook öffnen Java Basics - Anfänger-Themen 21
J Auf einem JLabel Linien Malen Java Basics - Anfänger-Themen 1
I @Entity Klassen, Service Beans etc. aus einem Share Projekt beziehen? Java Basics - Anfänger-Themen 26
R Images aus einem Array ausgeben Java Basics - Anfänger-Themen 3
XWing Randomizer mit einem String Java Basics - Anfänger-Themen 2
D OOP Array einem Objekt zuweisen Java Basics - Anfänger-Themen 2
O Zahlen aus einem char-array per char + Zeichen addieren Java Basics - Anfänger-Themen 2
S Bestimmte werte aus einem Array löschen Java Basics - Anfänger-Themen 2
S Ausgeben wie oft ein Wert in einem Array vorkommt Java Basics - Anfänger-Themen 7
N Einzelne Werte aus einem TreeSet auslesen Java Basics - Anfänger-Themen 2
N Welche Objekte kann man zu einem Set hinzufügen Java Basics - Anfänger-Themen 4
Kumora ArrayIndexOutOfBoundsException bei einem Sortierverfahren Java Basics - Anfänger-Themen 2
I Viereck / Rechteck Prüfung innerhalb einem bestimmten Bereich Java Basics - Anfänger-Themen 2
Distanz zwischen zwei Zeichenfolgen in einem String bestimmen Java Basics - Anfänger-Themen 5
Substring in einem String finden Java Basics - Anfänger-Themen 13
J Fehlerbehandlung an einem Beispiel Java Basics - Anfänger-Themen 8
I ResultSet aus meiner SQL-Abfrage in einem JTextfield ausgeben. Java Basics - Anfänger-Themen 1
I Innerhalb einem Bild ein Teil austauschen Java Basics - Anfänger-Themen 26
I Dateigröße von einem InputStream oder byte[] bekommen Java Basics - Anfänger-Themen 2
H Compiler-Fehler Klasse in einem Package wird nicht gefunden bzw. akzeptiert Java Basics - Anfänger-Themen 12
S Algorithmus entwicklen, der zu einem gegebenen Datum die Jahreszeit ermittelt Java Basics - Anfänger-Themen 13
B In einem Thread Endlosschleife beenden Java Basics - Anfänger-Themen 19
A Elemente in einem Array Java Basics - Anfänger-Themen 5
G Position einer unbekannten 3-stelligen-Zahl in einem String finden Java Basics - Anfänger-Themen 15
S Eine Variable in einem Array speichern Java Basics - Anfänger-Themen 5
T Methode, die prüft ob in einem Int-Array maximal 2 Zahlen enthalten sind, die größer als ihr Vorgänger sind Java Basics - Anfänger-Themen 5
berserkerdq2 Wie gebe ich den Pfad zu einer Datei an, die in einem Ordner in Eclipse ist? Java Basics - Anfänger-Themen 1
M Objekt in einem Objekt speichern Java Basics - Anfänger-Themen 9
J Speichern von zwei Variablen durch Auslesen aus einem Numberfield Java Basics - Anfänger-Themen 2
L Gridmuster in einem Array Java Basics - Anfänger-Themen 2
X Erste Schritte Hilfe bei einem kleinen Spiel. Java Basics - Anfänger-Themen 19
O Array mit einem Zeichen vergleichen Java Basics - Anfänger-Themen 1
B Brauche Hilfe zu einem Code Java Basics - Anfänger-Themen 5
J Zahlen bis zu einem bestimmten Grenzwert ausgeben Java Basics - Anfänger-Themen 11
P9cman Vokale in einem String überprüfen mittels Rekursion Java Basics - Anfänger-Themen 8
M Wie kann ich eine Methode aus einem Interface in eine Klasse implementieren, so dass sie ihre Funktion ausführt? Java Basics - Anfänger-Themen 7
M Wie kann ich in einem Konstruktor die Methode eines anderen Interfaces mit den jeweiligen Parametern aufrufen? Java Basics - Anfänger-Themen 8
Igig1 Wie lasse ich dir Werte in einem Array zusammenrücken? Java Basics - Anfänger-Themen 4
W Methode, die mit einem Datum arbeitet? Java Basics - Anfänger-Themen 22
Igig1 Welche Werte sind als default Werte in einem Array, der als Datentyp eine Klasse hat? Java Basics - Anfänger-Themen 1
Kiki01 Wie würde eine geeignete Schleife aussehen, die die relative Häufigkeit für jeden Charakter in einem Text bestimmt? Java Basics - Anfänger-Themen 3
C Hilfe bei einem Anfängerprojekt Java Basics - Anfänger-Themen 25
U Char zu einem String machen Java Basics - Anfänger-Themen 1
U Kann man bei Java gleich mehrere Bedingungen prüfen in der If, aber in einem "Satz"? Java Basics - Anfänger-Themen 1
Schniffi Nur bestimmte Bilder aus einem Array auf Image Button anzeigen lassen Java Basics - Anfänger-Themen 3
S Längster Pfad zwischen zwei Vertices in einem Graph Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben