Binärbäume

[niTeZ]

Hallo!

Habe ein kleines Problem mit Binärbäumen, genauergesagt mit dem Löschen.

Es gibt da 3 verschiedene Möglichkeiten. Links keine Elemente, Rechts keine Elemente, oder auf beiden Seiten Elemente. Das Programm soll in allen 3 Fällen funktionieren. Rekursiv wäre ein Vorteil. Habe mir dass ganze schon in etwa überlegt, nur weiß ich leider nicht genau, wie man dies umsetzen könnte. Das Suchen habe ich gerade noch hinbekommen, nur habe ich keinen Plan davon, wie der Code fürs Löschen dafür aussehen könnte.

Hoffe ihr könnt mir nen guten Lösungsweg geben, mit dem ich selbst den Code ohne weiteres schreiben kann, oder mir vielleicht sogar einen Code vorzeigen...(bitte vorzugsweise Delphi, ansonsten C/C++)

Danke im Vorraus.
nitez

 

[Patrick Kamin]

-

Ich denke mal, dass dein Baum geordnet ist. Wenn nur ein Kindknoten vorhanden ist, dann speicherst du die Referenz auf diesen, gehst eine Ebene höher, löschst den Knoten und hängst deinen gespeicherten Wert an die Position, die gerade frei geworden ist.

Wenn beide Folgeknoten vorhanden sind, dann nimmst du entweder den rechtesten oder den linkesten( die superlative sind hoffentlich klar geworden ) und ersetzt damit deinen zu löschen Knoten. Den Speicherplatz vom doppelten Element gibst du natürlich frei.