S
Hallo nochmal
Danke Volkard, jetzt kommen wir zu meiner Lösung und Vorstellung etwas näher. Aber ich weiß nicht, ob ein optimaler, linksorientierter binärer Baum, der die Heap-Bedingung erfüllt auch automatisch balanciert ist??? Was bedeutet balancier?
der Vektor soll dynamisch implementiert werden. Die Klasse als Template zu implementieren ist gut gedacht. Denn ich möchte auch verschiedene Objekte in ein Heap speichern, der sogar zwei Elemente in einem Knoten speichern kann, wie z.B. Heap <Autos> mit den Datenelementen "Sting name" und "int ID". template<class T, int n>. n steht für die Größe des Heaps, die dynamisch vom Benutzer eingegeben werden kann.
Da es sich um Objkete handelt müssen wir natürlich einen Kopierkonstruktor definieren und den Zuweisungsoperator überladen. Der Baum wird immer wieder nach dem Einfügen oder Löschen sortiert.
Einfügen: immer am weitesten links unten, dann bubble up, vorher wird verglichen, ob das Objekt im Vektor schon vorhanden ist. Es wird eine Exception ausgeworfen, sonst eingefügt.
Löschen: da braucht man die Methode deleteMin(). Es wird der kleinste Atom gelöscht--> die Wurzel. zuvor wird zum letzten Knoten gewandert und der letzte Knoten in die Wurzel kopiert, dann bubbleDown. Damit der Baum wieder sortiert wird. Die ANzahl der Knoten verringert sich um ein.
Also es gibt keine Lücken
Um den Heap ein- und auszulesen werden die beaknnten fstream Klassen verwendet. Das ist jetzt nicht wichtig für mich
PS: ich würde so gerne hier eine Grafik vom Baum einfügen, ist es möglich? Um das bildlich zu vernaschaulichen.
Liebe Grüße,
Soleil