Rekursives Löschen in Binärem Suchbaum

[ingobar]

Hallo zusammen,

ich bin gerade dabei eine binäen Suchbaum für integers zu schreiben. Habe aber Problem mit dem Löschen von Elementen. Das Problem ist dabei, dass das ganze rekursiv zu erledigen ist. Inzwischen bin ich aber gar nicht mehr so sicher, ob das geht.

Ich habe folgende Klasse Knoten:

[Java]
public class Knoten extends Baumelement{
// Attribute
public int daten;
public Baumelement linkerKnoten;
public Baumelement rechterKnoten;

//Konstruktor
public Knoten() {
daten = -1;
linkerKnoten = new Abschluss();
rechterKnoten = new Abschluss();
}

public Knoten(int newDaten) {
daten = newDaten;
linkerKnoten = new Abschluss();
rechterKnoten = new Abschluss();
}

//Methoden und Dienste
public Knoten insert(int newDaten) {
if (newDaten<daten) linkerKnoten = linkerKnoten.insert(newDaten);
else if (newDaten>daten) rechterKnoten = rechterKnoten.insert(newDaten);
return this;
}

public Baumelement delete(int daten) {
if (daten==this.daten) {
//Dieser Knoten muss gelöscht werden


//Unschöne Konstruktion mit instanceOf
if (linkerKnoten instanceof Knoten && rechterKnoten instanceof Knoten) {
//Fall 1: Zwei Nachfolger
//Ersetze den Inhalt des zu löschenden Knotens durch den größten Wert des linken Teilbaums
//oder alternativ durch den kleinsten Wert des rechten Teilbaumes.
//Lösche anschließend den entsprechenden Knoten mit der bei Fall 1 bzw. Fall 2 beschriebenen Methode.
return rechterKnoten.getMin();
} else {
if (linkerKnoten instanceof Abschluss && rechterKnoten instanceof Abschluss) {
//Fall 3: Der aktuelle Knoten ist ein Blatt und kann problemlos gelöscht werden
return new Abschluss();
} else {
//Fall 2: Nur einen Nachfolger
//Hier muss der left- bzw. der right-Zeiger des Vorgängerknotens
//auf den Nachfolger des zu löschenden Knotens gesetzt werden.
if (linkerKnoten instanceof Knoten) return linkerKnoten;
else return rechterKnoten;
}
}
} else {
//Aufruf weitergeben
if (daten>this.daten) {
//Löschaufruf weitergeben
rechterKnoten = rechterKnoten.delete(daten);
} else {
linkerKnoten = linkerKnoten.delete(daten);
}
}
return this;
}


}
[/code]

Und die Klasse Abschlusss:

public class Abschluss extends Baumelement {

    public Knoten insert(int newDaten) {
        return new Knoten(newDaten);
    }
    
    public Baumelement delete(int daten) {
        return this;
    }

}

Mein Problem ist, wie ich die Fallunterscheidung ohne instanceof lösen kann. Aber wie kann ich sonst entscheiden, ob ich ein Kind oder zwei Kinder habe etc. Soll ich ein Attribut kinderAnzahl einfügen? Oder für jeden Teilbaum erst die Tiefe ausrechnen lassen oder .....?

Wäre schön, wenn mir da jemand einen Tipp geben kann.

Ach ja, die Funktion getMin() habe ich noch nicht gemacht. Sie würde mir den kleinsten Knoten des rechten Teilbaums (also mit den größeren Elementen) liefern.

Ingo

 

[SlaterB]

definiere in Baumelement eine Methode boolean isAbschluss()
und implementiere die in beiden Klassen passend

kommt der kinderAnzahl ja nahe

 

[Mujahiddin]

Wie SlaterB würde ich das auch machen.
Beim Abschluss dann 'return false' und beim Knoten 'return true' und jenachdem, ob true oder false, ist es ein "Kind" oder keins.