Binärbaum aufstellen

[Dragon27]

Hallo Zusammen,

ich habe eine Frage bezüglich Binärbäume aufstellen.

In meinem Studienunterlagen heißt die Aufgabe "Skizzieren Sie einen nicht ausgeglichenen Binärbaum aus den Zahlen 42, 33, 75, 10, 41, 51, 99"

Nun bin ich folgendermaßen vorgegangen:

1. Werte aufsteigend Sotiert
2. Den Anfangsknoten habe ich mit der Formel (Anzahl der Blätter+1)/2 errechnet
3. Ersten Knoten (42) aufgeschrieben und dann die Formel wiederholt

So, nun kommt da auch tatsächlich die Musterlösung raus. Was mich daran irritiert ist, dass wenn die Anzahl der Blätter beispielsweise 8 wären mit meiner Formel 9/2 = 4,5 als ergebnis kommt. Welcher Knoten wird denn dann verwendet?

Oder ist auch meine vorgehensweise nicht richtig?

Danke für Eure Hilfe!

[Woyzeck]

Also, wenn kein ausgeglichener Binärbaum gefragt ist, kannst du auch einfach mit der Reihenfolge einfügen, die in der Aufgabe gegeben ist. Wichtig ist dann nur, dass die Binärbaumeigenschaft nicht verletzt wird (also Elemente im linken Teilbaum immer kleiner gleich der Wurzel und der rechte Teilbaum größer).

Wenn du einen ausgeglichenen Binärbaum haben willst, dann sortierst du das Feld und nimmst das mittlere Element als Wurzel. Als zweites Element nimmst du das mittlere der nun entstandenen Teilliste und dann das mittlere der rechten Teilliste.

Also bei folgenden Elementen: 1,2,3,4,5,6,7

fügst du in der Reihenfolge 4, 2, 6, 1, 3, 5, 7 ein.
(Natürlich gibt es noch andere Möglichkeiten, aber dies ist eine der funktionierenden)

Das mittlere Element findest du mit der von dir angegebenen Formel. Wenn dabei jetzt ein x,5 rauskommt, kannst du x oder x+1 als mittleres Element nehmen. Es sollte aber einheitlich sein. (Im Code will man ja schließlich an dieser Stelle keinen Zufall einbauen) Also entweder abrunden oder aufrunden.

Hoffe, ich konnte helfen.

Woyzeck