Java: Bäume Pfadlänge

[jati123]

Guten Tag!

Ich habe eine Problem bei der Lösung einer Aufgabe in Java (Eclipse).

Ich soll eine Operation in Java implementieren, die die Ausgeglichenheit in einem Binärbaum angibt z.B. 52%!

Zur Lösung des Problems benötige ich folgende Parameter:

- Anzahl der Knoten !!!Fertig!!!
- Maximale Pfadlänge !!!Fertig!!!

- Pfadlänge!!! (hier stecke ich fest)

Die Pfadlänge soll laut Aufgabenstellung die Summe der Knoten sein.


Beispiel:

Der Baum auf dem Bild hat eine Pfadlänge von !!16!!

Rechnung:

0 (Knoten ?50?) + 2*1 (Knoten ?35? und ?75?) + 4*2 (Knoten ?23?, ?43?, ?60?, ?77?) + 2*3 (Knoten ?40? und ?70?) = 16.


Vielen Dank für eure Hilfe im Voraus!!!

 

[Adelhorst]

Hallo.
Ich glaube mit einer Berechnung 'a la Formel', so wie in deinem Beispiel angedeutet, wirst du nicht weiterkommen.

Wenn du alle vorhandenen Zahlen in dem Baum suchen lässt und dabei die 'angetroffenen/überquerten' Knoten addierst, wirst du eher zu einem Ergebnis kommen.

 

[stg]

Vergleiche rekursiv die Tiefe des linken Teilbaumes und die des rechten Teilbaumes

 

[jati123]

Hallo

vielen Dank für die Antworten bis jetzt!

@stg bin ich da mit dem Thema Traversierung auf dem richtigen Weg?

Gruß

 

[stg]

Ja, mit Tiefensuche lässt sich das ganz einfach umsetzen. Du musst dir nur zusätzlich die jeweils aktuelle Tiefe merken.