vollständig ausgeglichener Baum

ditsche

ich soll ein Programm schreiben, das aus einer liste einen vollständig ausgeglichenen Baum macht.

Ich versuch und versuch es nochmal, aber ich hab keine Idee, wie ich das machen soll. Woher weiß man, wo grade der nächste Knoten hingesetzt werden muss?

Ich wäre dankbar für Ideen und Vorschläge!!!

(Morgen ist Abgabe...)

Gruß

Da hat sich aber jemand nicht viel Mühe beim Verfassen des Beitrags gegeben.

Apollon

Eine Liste kann als Baum 1er Ordnung duchgehen.

ditsche

okay...
also ein binärer baum soll es sein.

F¨ur einen bin¨aren Baum B bezeichne |B| die Anzahl der Knoten des Baumes. Mit
LB und RB seien der linke und rechte Teilbaum von B bezeichnet. Ein bin¨arer
Baum heißt vollst¨andig ausgeglichen, wenn f¨ur jedes Paar von linkem und rechtem
Teilbaum gilt:
0 ≤ |LB| − |RB| ≤ 1
Entwickeln Sie eine Funktion ausgeglbaum, die zu einer vorgegebenen Anzahl
von n Knoten einen vollst¨andig ausgeglichenen Baum aufbaut!
Vorgabe: knoten * ausgeglbaum(int n);
Der R¨uckgabewert der Funktion zeigt nach Durchlauf auf die Wurzel des Baumes.

anordnung der knoten ist nicht wichtig im moment. die frage ist nur, wie man ab zB ebene 4 weiß, wo der nächste knoten hin muss

Apollon

Wenn k ein Knoten ist, dann ist Knoten 2k der linke Sohn von k und 2k+1 der rechte Sohn. Natuerlich fuer 2k und 2k+1 < |B|. Demnach sind der 2te und der 3te Knoten Soehne des ersten.

imhotep

Soll die Reihenfolge der Knoten eine Rolle spielen?
Meist ist es so linkerSohn < Vater <= rechterSohn.

Wenn nicht: (Konzept)

knoten * ausgeglbaum(int n){
  int temp;
  knoten * vater, rechterSohn, linkerSohn;
  if (n == 0) return 0; // brauch nix zu machen
  vater = new Knoten();
  if (n > 3) {
    temp = (n - 1) / 2;
    linkerSohn = ausgeglbaum( n - ( temp + 1) );
    rechterSohn = ausgeglbaum( temp );
    vater.lSohn = linkerSohn;
    vater.rSohn = rechterSohn;
  } else {
    if (n == 3) vater.rSohn = new Knoten();
    if (n > 1) vater.lSohn = new Knoten();
  }
  return vater;
}

otze

nimm deine Startliste. nimm das element genau in der mitte. dieses element ist die Wurzel. dann teilst du liste in 2 teile: der teil rechts vom Knoten, und der teil links vom Knoten. nimm vom linken teil wieder die hälfte, das ist das linke kind der wurzel. genauso verfährst du rechts. dann teilst du die 4 übrigen teilstücke. das machst du solange, bis alle Kinder im Baum sind.

Beispiel(jede zahl ein element)

1. startliste

1 2 3 4 5 6 7

2. mittelelement nehmen

1 2 3   5 6 7
      4

3. teillisten teilen

1   3   5   7
  2       2
    \   /
      4

4. die 4 teillisten anhängen

1   3   5   7
 \ /     \ /
  2       6
    \   /
      4

und tada: ist die liste sortiert, hast du am ende einen gut ausbalanzierten binärbaum

Pellaeon

*lol* ob das der Sinn ist die Liste vorher zu sortieren und dann erst den Baum aufzubauen

volkard

Pellaeon schrieb:

*lol* ob das der Sinn ist die Liste vorher zu sortieren und dann erst den Baum aufzubauen

ewrst in ein array kopieren, dann sortieren, dann baum draus machen. fühlt sich recht billig an, finde ich.

Pellaeon

Ok zugegeben: wenn die Aufgabestellung so bleibt und danach nichts mehr am Baum geändert wird, mag das gehen. Sobald aber der Baum erweitert wird und dabei ausgeglichen bleiben soll ...

otze

Pellaeon schrieb:

*lol* ob das der Sinn ist die Liste vorher zu sortieren und dann erst den Baum aufzubauen

wenn der startpunkt eine liste ist geht kaum billiger(ausser vielleicht volkards array ;))