Binärbaum getSize

Status
Nicht offen für weitere Antworten.

Johnny2

Mitglied
Guten Abend zusammen,

hab mal wieder eine Frage.

Hab nem Binärbaum programmiert (bzw. bin dabei), der zum Speichern von Objects dient.

Um jetzt mit der Methode getSize() die größe bzw Anzahl der Elemente des Baumes rausfinden, hab ich mir das so gedacht:

Ich beginne bei der Wurzel und gehe immer den "rechtesten" Weg, sollte es zwei Abzweigungen geben, speichere ich den Knoten auf einem Stack und gehe den rechten Weg. Irgendwann bin ich damit, ganz unten gelandet. Dann gehe ich nach oben jeweils zu einem "Vater" des Knotens und vergleiche ob er der das oberste Element am Stack ist:

Wenn ja, geh ich den Linken Zweig nach unten
Wenn nicht, dann geh ich zu dessen Vater

dies wird solange gemacht bis ich beim Wurzelknoten wieder angelangt bin und auch der Stack leer ist.

Ist der Gedankenansatz richtig, oder mach ich das viel zu kompliziert?
 

0x7F800000

Top Contributor
äää... jain.

Das mit dem Stack ist theoretisch richtig, aber kein Mensch würde da jemals irgendwas explizit mit einem Stack bauen. Das erledingt der Callstack ganz von alleine, wenn du das alles schön rekursiv ausformulierst (das sind dann 3 zeilen). Würdest du versuchen, dieses verhalten selbst nachzuahmen, so ist zum einen mit Performanceverlusten zu rechnen, zum anderen wird's hässlich wie die Pest und 20-30 zeilen länger als nötig.

Rekursion ist also das Zauberwort. Ist es praktisch immer, wenn es um binäre bäume geht.
 

Johnny2

Mitglied
Ok, werd mich mal über den Callstack (=>Anfänger) informieren. Wenn's Probleme gibt meld ich mich nochmal
 

Johnny2

Mitglied
Aber der Denkansatz war schon gut. Wenn ich so gut bin, werd ich danach mal ein bisschen im Linux-Kernel aufräumen :D
 

0x7F800000

Top Contributor
what?... ???:L

<denkanstoß>
schreib's rekursiv hin, und alles erledigt sich von selbst.
</denkanstoß>
^^ :roll:
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Wie greift man auf die Knoten in einem Binärbaum zu? Java Basics - Anfänger-Themen 5
T Binärbaum-Suche Implementation Java Basics - Anfänger-Themen 6
A Binärbaum rekursiv durchsuchen und Referenz zurückgeben Java Basics - Anfänger-Themen 4
D Werte aus einem BinärBaum in einem Array speichern Java Basics - Anfänger-Themen 1
D Binärbaum Blätter finden und Ausgeben Java Basics - Anfänger-Themen 22
O BinärBaum einfügen Java Basics - Anfänger-Themen 13
E Erste Schritte Testklasse Binärbaum Java Basics - Anfänger-Themen 10
void19 Methoden Binärbaum Inorder Traversierung in Array speichern Java Basics - Anfänger-Themen 1
A Größten Eintrag aus Binärbaum löschen Java Basics - Anfänger-Themen 4
L Ganzen BinärBaum ausgeben? Java Basics - Anfänger-Themen 3
L Binärbaum (Stammbaum) Java Basics - Anfänger-Themen 8
S Binärbaum in PreOrder in ArrayList speichern Java Basics - Anfänger-Themen 0
J Methoden Binärbaum, Traversierung in Array speichern Java Basics - Anfänger-Themen 18
K BinärBaum 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
C Binärbaum mit grafischer Ausgabe Java Basics - Anfänger-Themen 0
J Binärbaum formatiert ausgeben. Java Basics - Anfänger-Themen 7
P Listen sortieren mit Binärbaum gibt keine Ausgabe ab 10000 Integern Java Basics - Anfänger-Themen 14
E Binärbaum - von rekursiv zu iterativ Java Basics - Anfänger-Themen 10
W Größtes Element im unsortierten Binärbaum Java Basics - Anfänger-Themen 7
N Generischer Binärbaum - löschen Java Basics - Anfänger-Themen 1
M Binärbaum mit parent-Zeigern Java Basics - Anfänger-Themen 1
B Methoden BinärBaum als String Knoten löschen Java Basics - Anfänger-Themen 5
S Binärbaum kopieren Java Basics - Anfänger-Themen 6
B Binärbaum mit java implementieren! Java Basics - Anfänger-Themen 5
D Binärbaum Suche Java Basics - Anfänger-Themen 5
D Binärbaum probleme Java Basics - Anfänger-Themen 4
P Binärbaum - Primärschlüssel Java Basics - Anfänger-Themen 3
X Fehler Binärbaum Java Basics - Anfänger-Themen 6
PaulG Fragen zu Binärbaum Java Basics - Anfänger-Themen 21
N Binärbaum/Implementierung Java Basics - Anfänger-Themen 9
P Binärbaum Ordnungsproblem Java Basics - Anfänger-Themen 8
P Generischer Binärbaum (compareTo Frage) Java Basics - Anfänger-Themen 4
P einen binärbaum implementieren Java Basics - Anfänger-Themen 4
M Binärbaum - Problem bei Knoten anhängen / löschen Java Basics - Anfänger-Themen 5
B Binärbaum höhe herausfinden Java Basics - Anfänger-Themen 12
L Rot Scharz Baum von Binärbaum erben Java Basics - Anfänger-Themen 9
S Klassen Aufgabe: Binärbaum überprüfen Java Basics - Anfänger-Themen 16
S Binärbaum Java Basics - Anfänger-Themen 9
S Variable Parameterliste in Binärbaum Java Basics - Anfänger-Themen 2
N BinärBaum Hilfestellung Java Basics - Anfänger-Themen 8
S Binärbaum prüfen, ob sortiert oder unsortiert Java Basics - Anfänger-Themen 6
W Binärbaum zahlen addieren Java Basics - Anfänger-Themen 7
S Binärbaum - Klasse Knoten - Methode Suchen Java Basics - Anfänger-Themen 5
S Binärbaum Java Basics - Anfänger-Themen 7
I Binärbaum Java Basics - Anfänger-Themen 5
S Bitte um Hilfe beim unsortierten Binärbaum!! Java Basics - Anfänger-Themen 6
P Fragen zum Binärbaum Java Basics - Anfänger-Themen 3
S Binärbaum implementieren Java Basics - Anfänger-Themen 6
K Tiefe im Binärbaum Java Basics - Anfänger-Themen 2
G generischer binärbaum Java Basics - Anfänger-Themen 9
G Binärbaum und Wrapperklassen Java Basics - Anfänger-Themen 6
F Binärbaum codieren. Codeproblem! Java Basics - Anfänger-Themen 4
D rekursion im binärbaum Java Basics - Anfänger-Themen 11
0 Binärbaum als verkettete Liste Java Basics - Anfänger-Themen 3
T Binärbaum - noch ein "klitzekleiner Fehler" Java Basics - Anfänger-Themen 4
B Binärbaum auf Vollständigkeit prüfen Java Basics - Anfänger-Themen 15
G Frage zur einfügen in einem Binärbaum Java Basics - Anfänger-Themen 21
G Binärbaum grafisch darstellen Java Basics - Anfänger-Themen 4
R getStyle() getSize() Java Basics - Anfänger-Themen 17
G Wann am besten getSize() aufrufen? Java Basics - Anfänger-Themen 6
J label.getSize() gibt 0 ? Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben