Binärer Suchbaum - Object löschen

Neue Frage »

Auf diesen Beitrag antworten »
stift22 Binärer Suchbaum - Object löschen

Hallo.
Ich habe einen binären Suchbaum. Dieser verwaltet (hat) einen Binärbaum. Nun möchte ich ein Blatt löschen (linker und rechter Teilbaum ist leer).

Warum geht das so nicht? Ich verwende die Abiturklassen.

if getRightTree.isEmpty and getLeftTree.isEmpty
then
begin
self.getLeftTree.destroy;
self.getRightTree.destroy;
self.hBinaryTree.getObject.destroy;
end;
 
Auf diesen Beitrag antworten »
Karlito

Hallo,

die Informationen, die Du uns gibst sind leider etwas dürftig... Welcher Fehler tritt denn auf? Etwas mehr vom Quelltext wäre vlt auch hilfreich.

Vermutung: Es sieht so aus, als ob Du einfach einen Knoten löschst. im darüberliegenden Teil des Baumes gibst du aber nicht bekannt, dann der Knoten gelöscht ist. D.h. ich vermute, Du musst im Vorgängerknoten noch bekannt geben, dass der linke oder rechte Teilbaum gelöscht wurde...

VG,

Karlito
Auf diesen Beitrag antworten »
stift22

Hi,

es tritt kein Fehler auf, aber es geschieht einfach nichts, wenn ich auf löschen gehe^^
Bei self.hBinaryTree.getObject.destroy; müsste doch eigentlich das Object gelöscht werden - oder? Also die Teilbäume muss ich ja dann auch noch vernichten, aber müsste ja zum Testen auch erstmal ohne gehen, oder? Der macht einfach gar nichts...und das soll in 3 Zeilen lösbar sein (linker Baum weg, rechter Baum weg und Inhaltsobject weg)...
Auf diesen Beitrag antworten »
Karlito

Hallo,

OK, ich weis noch nicht genau was das Problem ist.
- Wie ist deine Aufgabe genau formuliert?
- Wo genau befinden wir uns, also in welcher Klasse (worauf zeigt self)?

VG,

Karlito
 
Auf diesen Beitrag antworten »
stift22

Ich befinde mich in der Unit BinarySearchTree.
Den Suchbaum benutzen wir so, dass dieser einen Binärbaum verwaltet. Wir implementieren die Abiturklassen. Es geht gerade um remove, also das Löschen von bestimmten Objecten eines Suchbaumes.
Bisher siehts so aus, funktioniert aber nicht im Geringsten großes Grinsen

procedure TBinarySearchTree.remove(pItem: TItem);
var hilfsbaum: TBinaryTree;
lTree,rTree: TBinarySearchTree;
loesche : TObject;
begin
if (not self.isEmpty) and (pItem <> nil)
then
if self.getItem.isEqual(pItem)
then
if getRightTree.isEmpty and getLeftTree.isEmpty
then
begin
self.getLeftTree.destroy;
self.getRightTree.destroy;
self.hBinaryTree.getObject.destroy;
end
else
if self.getRightTree.isEmpty // im rechten Teilbaum nichts drin
then
begin
//hatte ich mir erst überlegt
lTree := self.getLeftTree;
self.hBinaryTree.getObject.destroy;
self.hBinaryTree := lTree.hBinaryTree;
{ oder so besser????
lT := hBinaryTree.getLeftTree.getLeftTree;
rT := hBinaryTree.getLeftTree.getRightTree;
loesche := hBinaryTree.getObject;
hBinaryTree.setObject(hBinaryTree.getLeftTree.getObject);
loesche.destroy;
hBinaryTree.setLeftTree(lT);
hBinaryTree.setRightTree(rT);
}
end
else
if self.getleftTree.isEmpty
then // linker Teilbaum leer
begin // Objekte und Teilbäume umhängen
//gleiches wie oben
rTree := self.getRightTree;
self.hBinaryTree.getObject.destroy;
self.hBinaryTree := rTree.hBinaryTree;
{
lT := hBinaryTree.getRightTree.getLeftTree;
rT := hBinaryTree.getRightTree.getRightTree;
loesche := hBinaryTree.getObject;
hBinaryTree.setObject(hBinaryTree.getRightTree.getObject);
loesche.destroy;
hBinaryTree.setLeftTree(lT);
hBinaryTree.setRightTree(rT);
}
end
else
begin //beide teilbäume voll
hilfsbaum := self.hBInaryTree.getLeftTree;
while not hilfsbaum.getRightTree.isEmpty do
begin
hilfsbaum.getRightTree;
end;
loesche := hilfsbaum.getObject; //Object ganz rechts
self.remove(TItem(hilfsbaum.getObject)); //den Zipfel löschen
self.hBinaryTree.getObject.destroy; //altes Inhaltsobject
self.hBinaryTree.setObject(loesche); //zipfel darein hängen
end
else // wenn object noch nicht gefunden: rekusiver aufruf
begin
if self.getItem.isLess(pItem)
then self.getLeftTree.remove(pItem)
else self.getRightTree.remove(pItem);
end;
end;

Reicht das an Infos? Also wie gesagt, Fehlermeldungen bekomme ich nicht, der macht aber einfach nichts..
Auf diesen Beitrag antworten »
Karlito

Hallo,

Ich kenne die Abiturklassen nicht.

Dass ein Knoten sich selbst löscht ist nicht sinnvoll... (So verstehe ich deinen Quelltext auf die schnelle)

Du brauchst eine Verwaltungsstruktur, welche den Baum hält. D.h. Es muss ein Objekt geben, was die Wurzel des Baumes kennt. Die Klasse des Objektes muss auch die Löschfunktion implementieren.

Der Grund ist: Angenommen du löschst ein das Wurzelelement eines Teilbaums. Dann müssen die Kinder des Baumes umgehängt werden. Der Elternknoten des Knotens in dem du dich befindest ist jedoch nicht bekannt, so dass die Kinder nicht umgehangen werden können. Schlimmer noch: wird der Baum leer und du hältst dir den Baum in einer Variable, so Löscht sich der Baum selbst. Greifst du dann wieder auf die Variable zu, so führt das zu einem Fehler.

VG,

Karlito
Auf diesen Beitrag antworten »
stift22

Ja, richtig löschen kann man mit diesen Klassen nicht, aber wir müssen die benutzen fürs Abitur - ich hätte das auch ganz anders angegangen, aber geht halt nicht.

Wenn du es jetzt so machen müsstest, warum wird das Blatt nicht gelöscht mit dem self.hBinaryTree.getObject.destroy;

Ich bin nun nach dem Suchen an dem Knoten angekommen, wo das Inhaltsobjekt gelöscht werden soll. Nun nimmt mein Suchbaum sich den BInärbaum, den er verwaltet, und sagt dem, dass der sein Inhaltsobject löschen soll... ja und da der Suchbaum nur das verwalten kann, was der hBInaryTree noch hat, wäre die Sache für mich eigentlich klar :/ Wo liegt der Fehler??
Auf diesen Beitrag antworten »
Karlito

Zitat:
Original von stift22
Wenn du es jetzt so machen müsstest, warum wird das Blatt nicht gelöscht mit dem self.hBinaryTree.getObject.destroy;


Das kann ich dir leider nicht sagen... Dazu müsste ich die Klassenstruktur besser kennen. Gibt es diese Online?

VG,

Karlito
Auf diesen Beitrag antworten »
stift22

standardsicherung.nrw.de/abitur-gost/fach.php?fach=15
Dann unter Materialien für Delphi ab 2012, S.13-S.15 in der PDF Augenzwinkern
Auf diesen Beitrag antworten »
Karlito

schaue ich mir mal an, komme aber wahtscheinlich leider bis mittwoch oder donnerstag nicht dazu

bis dahin, guten rutsch...

VG,

Karlito
Auf diesen Beitrag antworten »
stift22

Ja, danke, guten Rutsch Augenzwinkern

Und über weitere Ideen zu meinem Problem bin ich auch im nächsten Jahr dankbar großes Grinsen
Auf diesen Beitrag antworten »
stift22

Schreibt mir noch einer zurück? Schule fängt wieder an - bis dahin sollte ich das mal gecheckt haben Augenzwinkern
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »