sorted BinTree & delete Methode

[G10101]

Hallo, ich habe ein Problem bezüglich dem Löschen in sortierten Binärbaumen.
Die Klasse eines normalen Binärbaums habe ich wie folgt deklariert.
[Java]
public class BinTree {
private int value;
private BinTree leftSon, rightSon;

// Konstruktor
public BinTree (int v, BinTree l, BinTree r){
value = v;
leftSon = l;
rightSon = r;
}

public int val(){
return value;
}

public BinTree lson(){
return leftSon;
}

public BinTree rson(){
return rightSon;
}

public void setVal(int v){
value = v;
}

public void setLson(BinTree l){
leftSon = l;
}

public void setRson(BinTree r){
rightSon = r;
}

//Ist Blatt?
public boolean isleaf(){
return leftSon == null && rightSon == null;
}

//linkester Knoten
public BinTree leftmost(){
BinTree p = this;
BinTree q;
while( (q = p.lson()) != null){
p=q;
}
return p;
}

}
[/Java]

In einem sortierten Baum ist der linke Knoten im < als die Wurzel und der rechte Knoten immer > als die Wurzel.

Wenn man einen Knoten löscht, muss dieser durch den linkesten Knoten im rechten Teilbaum ersetzt werden und der natürlich gelöscht werden. Existiert nur ein rechter Knoten, der keine linken Söhne hat, so nimmt dieser den Platz an der Wurzel ein.

Ich habe mir jetzt 2 verschiedene, sehr ähnliche Methoden zum löschen überlegt. Eine mit Rekursion, die andere ohne.

[Java]
public static void delete(BinTree bt, int x){
//Baum nicht vorhanden => nix machen
if(bt == null)
return;

//zu löschender Wert in der Wurzel des BinTree bt
if (bt.val() == x){
//1. Fall: bt ist Blatt
if(bt.isleaf()){
bt = null;
}
//2. Fall: bt hat nur einen Sohn, entweder lson oder rson
else if(bt.lson() == null && bt.rson() != null){
bt = bt.rson();
}
else if(bt.lson() != null && bt.rson() == null){
bt = bt.lson();
}else{
//3. Fall: bt hat 2 Söhne
bt.setVal(bt.rson().leftmost().val()); // linkesten Knoten vom rechten Teilbaum in bt schreiben und löschen
if(bt.rson().leftmost().rson() != null){ //hat linkester Knoten selbst noch rechten Teilbaum, dann "hochziehen"
bt.rson().leftmost().setVal(bt.rson().leftmost().rson().val());
bt.rson().leftmost().setLson(bt.rson().leftmost().rson().lson());
bt.rson().leftmost().setRson(bt.rson().leftmost().rson().rson());
}
else{ //hat linkester KEINEN rechten Baum (ist also Blatt), dann den linkesten löschen
//Sonderfall: linkester Knoten im rechten Baum ist direkter, rechter Knoten & Blatt
if(bt.rson().isleaf())
bt.setRson(null);
else{
//Vater von linkestem Knoten finden
BinTree p = bt.rson();
BinTree father = bt;
while(p.lson() != null){
father = p;
p = p.lson();
}
father.setLson(null);
}
}
}
}else if (x < bt.val()) delete(bt.lson(), x); //Rekursion ...
else if (x > bt.val()) delete(bt.rson(), x);
}
[/Java]

2. Methode

[Java]
public static boolean deleteX(BinTree bt, int x){
BinTree son = bt, father = null;

//Knoten zum löschen suchen
while( (son != null) && (x != son.val()) ){
father = son;
if(x > son.val())
son = son.rson();//rechts suchen
else son = son.lson();
}

//zu löschender Knoten im Baum?
if(son != null){
if(son.isleaf()){
if(father == null)
bt = null;
else if(father.lson().val() == son.val())
father.setLson(null);
else father.setRson(null); //geht das auch nur durch son = null; ??
}
else if(son.lson() == null){ //nur rechten Sohn => dieser ist Ersatz
if(father == null) //Spezialfall: löschender Knoten ist Wurzel
bt = son.rson();
else if(father.lson().val() == son.val())
father.setLson(son.rson());
else father.setRson(son.rson());
}
else if(son.rson() == null) //nur linken Sohn => dieser Ersatz
//if(father == null)
//bt = son.lson();
//else
son = son.lson();
//father.setLson(son.lson());
else{
//Fall: 2 Söhne
BinTree s = son.lson(); //s ist linker Knoten von zu löschendem Knoten son
BinTree f = son; //Vater am Anfang ist zu löschender Knoten
while(s.rson() != null){ //rechtesten Knoten im linken Teilbaum finden
f=s;
s=s.rson();
}
if(s.lson() != null) //hat rechtester Knoten im linken Teilbaum aber noch linken Teilbaum? => umhängen
f.setRson(s.lson());
else f.setRson(null); // sonst Knoten löschen
son.setVal(s.val()); //zu löschenden Knoten auf Wert vom "nachfolgenden"
}

return true;
}
else
return false;
}
[/Java]

Probleme gibt es irgendwie beim löschen von Blättern und Knoten, die nur einen rechten Knoten besitzen. Liegt es daran, dass bei Methoden Aufrufen nur Kopien erstellt werden und dann im wirklichen Baum nichts gelöscht wird? Irgendwie sieht die erste Methode für mich richtig aus, aber naja ...

folgender Test ergbit z.B. folgende Ausgabe der Infix Darstellung.
[Java]
printArray(infix(tree7));

boolean success = deleteX(tree7, 4);
System.out.println("Löschen erfolgreich: " + success);
printArray(infix(tree7));

success = deleteX(tree7, 6);
System.out.println("Löschen erfolgreich: " + success);
printArray(infix(tree7));
[/Java]

1 2 3 4 5 6 7
Löschen erfolgreich: true
1 2 3 5 6 7
Löschen erfolgreich: true
1 2 3 5 5


Vielen Dank schonmal

 

[1001010100]

Hat sich erledigt, vielen Dank für die hilfe

 

[21456789]

Hat sich erledigt, vielen Dank für die hilfe

Läuft das programm?