kompletter baum

[christin05]

Hallo alle zusammen,

weiß jemand wie man eine Methode schreibt, welche zuerst überprüft ob ein binärer Suchbaum komplett ist oder nicht, falls nicht wird dieser durch die Methode vervollständigt.

Ich wäre über hilfreiche Tipps sehr dankbar

 

[Gucky]

Das etwas komplett ist, ist dadurch definiert, dass, in diesem Fall, alles drin ist, was drin sein soll.
Also durchsuchst du den Baum nach allen Werten, die drin sein sollen, oder performanter, du durchsuchst den Baum vollständig und "hakst" alles, was rein soll ab. Ist am Ende alles abgehakt, ist der Baum vollständig.
Zum Vervollständigen müsste ich wissen, welche Methoden der Baum schon anbietet oder ob er nur eine Datenstruktur ist.

 

[CSHW89]

Ich glaube vollständig meint hier, dass man kein Element mehr hinzufügen kann, ohne die Höhe des Baumes zu verändern, bzw. oberhalb der untersten Ebene haben alle Knoten zwei Kinder.
Wenn die Höhe 'h' und die Anzahl 's' bekannt ist: prüfe ob s = 2^(h+1) - 1. Ansonsten durchlaufe den Baum, und berechne dabei die Höhe und Anzahl.

lg Kevin