Geschrieben von as_string am 12.07.2017 um 20:20:
Ah, ok, daran liegts.
Ideal ist es, wenn der Baum richtig "aufgefüllt" ist. Du brauchst ja mindestens eine bestimmte Höhe des Baumes für eine bestimmte Anzahl von Knoten. In Deinem Beispiel sind es z. B. 7 Knoten. Der Baum hat eine Höhe von 3.
Bei einem Baum mit Höhe 1 kannst Du nur einen Knoten unterbringen.
Bei einem Baum mit Höhe 2 kommen nochmal doppelt so viele (also 2) dazu, macht insgesamt 3.
Bei einem Baum mit Höhe 3 kommen nochmal doppelt so viele (also 4) dazu, macht insgesamt also 3+4=7
Bei einem Baum mit Höhe 4 kommt nochmal doppelt so viele (also 8) dazu, macht insgesamt 7+8 = 15.
Insgesamt hast Du also bei einem Baum mit Höhe h maximal Platz für log
2(h)-1 Plätze.
Du könntest aber einen Baum auch so auffüllen, dass Du die Höhe nicht so gut ausnutzt: Stell Dir in Deinem Beispiel vor, dass der Knoten B und seine Kinder D und E gar nicht vorhanden wären und auch F fehlen würde. Dann wäre die Höhe immer noch 3 (von A bis G über C), aber insgesamt wären es nur 3 Knoten, die man auch in einen Baum mit Höhe 2 unterbringen könnte. Das wäre dann ein unbalancierter Baum.
Deutlicher wird es, wenn man einen größeren unbalancierten Baum betrachtet wie in
https://de.wikipedia.org/wiki/Balancierter_Baum gleich das erste Bild.
Das Problem mit dem Array ist aber: Ein solcher Baum kann dazu führen, dass Du "Löcher" im Array hättest. Das Array muss ja immer eine Größe von 2^h-1 haben, also 1, dann 3, dann 7, dann 15, etc. Wenn Du aber nur 3 Elemente hast, dann sind ja 4 der sieben Plätze im Array unbelegt.
In unserem "entarteten" Beispiel, bei dem nur noch A, C und G übrig sind, müssten diese immer noch am selben Platz im Array sein, aber alle anderen Plätze müssten leer sein. Die Frage ist nun: Wie kann man diese leeren Plätze markieren?
Ich weiß nicht so genau, was die als Antwort da hören wollen. Man könnte sich ein ungültiges Zeichen überlegen, das man da rein schreibt. Aber welches Zeichen ist denn gültig, welche nicht? Das geht aus der Aufgabe nicht hervor. Wenn man ein char-Array hätte, könnte man z. B. eine 0 rein schreiben anstelle eines gültigen ASCII Werts oder so.
Das angesprochene Problem ist natürlich, dass man bei großen unbalancierten Bäumen dann eine Menge Stellen im Array unbelegt hätte und deshalb Speicherplatz verschwenden würde.
Gruß
Marco