Pfadlänge eines binären Suchbaums

[Gast]

hallo

bin gerade am java lernen für die prüfung nächste woche, und beschäftige mich grade mit den binären suchbäumen. contains, add, height, size hab ich schon alles erfolgreich in mein Hauptprogramm eingefügt und auch getestet.
nun soll ich aber die pfadlänge des Baumes berechnen, und finde dazu weder im skriptum noch im internet irgendetwas hilfreiches...
wäre nett wenn mir da vielleicht jemand helfen könnte..

 

[Backwardsman]

mmh, woran liegts denn? an der definition von "pfad", "pfadlänge" oder einfach nur am programmieren???

 

[Guest]

es geht eher um die umsetzung... rein theoretisch ist die pfadlänge doch die Summe der Ebenen aller Knoten des Baumes, dh 1x Knoten der 1. Ebene + 2x Knoten der 2x Ebene + usw.... aber wie programmier ich das?

 

[Gast2]

Das ist in einer Zeile erledigt - die entsprechende Funktion findest du im Package (Klasse?) math .... die Lösung hat jede Erklärung eines Binären Baumes

 

[Landei]

Wenn du n Elemente in einen (balancierten) binären Baum packst, wieviel "Ebenen" (also "worst-case" Pfadlängen) bekommst du? 1 Element gibt 1 Ebene, 3 Elemente geben 2 Ebenen, 7 Elemente geben 3 Ebenen, (2^k)-1 Elemente geben k Ebenen. Und jetzt Runden und ein wenig Schulmathematik...