Heap Insert Aufgabe

[Juney]

Hallo zusammen,

für die FH muss ich die folgende Aufgabe lösen:

Wir betrachten einen binären Baum, der in seinen Knoten nur ganze Zahlen abspeichert. Dieser

Baum soll in allen Ebenen bis auf die unterste vollständig gefüllt sein. In der untersten

Ebene müssen die Knoten linksbündig angeordnet sein (d.h. er weist Heap-Struktur auf, muss

aber nicht die Heap-Eigenschaft erfüllen). Der Baum liegt in der von uns definierten Struktur

mit Zeigern vor, nicht als Array. Zusätzlich zum immer vorhandenen WURZEL-Zeiger

besitzt unser Baum einen Zeiger LAST, der auf das rechteste Blatt in der untersten

Baumebene verweist.

Schreiben Sie einen Algorithmus in unserer allgemeinen Algorithmen-Schreibweise, der als

Parameter den WURZEL-Zeiger, den LAST-Zeiger und einen Zeiger auf einen „losen“

Knoten erhält, bei dem nur die ganze Zahl ausgefüllt ist. Der Algorithmus soll den Knoten,

den er als Parameter erhält, als neues LAST-Element in den Baum einfügen. Der LASTZeiger

muss dann entsprechend angepasst werden, während sich die übrige Struktur des

Baumes nicht ändern darf.

Kann mir jemand damit weiterhelfen?

Freue mich über eure Antworten

[iNvAsIoN]

Ist doch nur ein verbiegen von Zeigern im Baum. Heapeigenschaft ist, jedes Kind ist kleiner als der zugehoerige Vater. Am besten du malst dir 2 Baeume Zur Loesung auf. Der eine hat den letzten Knoten im linken Teilbaum der Wurzel und der andere in der rechten. Dann musst du ueberlegen wie du die Zeiger verbiegst, gegeben ist ja ein Zeiger auf den Lastknoten, das sollte dir helfen. Wenn du das Bild gemalt hast sollte das klarer werden. Danach gehst du folgendermassen vor um Fehler abzufangen. Es besteht die moeglichkeit das der Baum leer ist-> muss beachtet werden. Es besteht die moeglichkeit das der Lastzeiger gleich dem Wurzelzeiger ist usw. solche Fehler muessen abgefangen werden.

MfG Inva