Ich baue einen binären Baum auf und möchte mit der delete()-Methode die Elemente wieder löschen.
das Löschen des rechten und linken Teilbaumes funktioniert auch, aber soblad ich die Wurzel löschen möchte wird der Baum neu erstellt, zb.
-füge ich die zahlen 2, 1, 3 ein
-möchte dann die Wurzel 2 löschen, hängt mein Programm die 1 an die 3 ran
sieht jemand meine Fehler?
Vielen dank schonmal im voraus!
das Löschen des rechten und linken Teilbaumes funktioniert auch, aber soblad ich die Wurzel löschen möchte wird der Baum neu erstellt, zb.
-füge ich die zahlen 2, 1, 3 ein
-möchte dann die Wurzel 2 löschen, hängt mein Programm die 1 an die 3 ran
Code:
public boolean delete(Comparable x)
{
TreeNode parent = root,
nodeR = root.getRight(),
nodeL = root.getLeft(),
node = null,
child = null,
tmp = null;
if(x.compareTo(parent.getData())==0)
{
System.out.println("root"+parent);
node = root;
}
else if(x.compareTo(parent.getData())<0)
{
System.out.println("nodeL" +nodeL);
node = nodeL;
}
else
node = nodeR;
System.out.println("Wurzel "+root.getData());
System.out.println("zu loeschendes Element "+x);
//zu loeschenden Knoten suchen
while(node != null)
{
int cmp = node.getData().compareTo(x);
System.out.println("cmp "+cmp);
if(cmp == 0)
break;
else
{
System.out.println("else");
System.out.println("parent = "+node.getData());
parent = node;
System.out.println(parent.getData() + " = node");
//cmp>0 entweder node.getLeft() oder node.getRight()
System.out.println("1:(cmp["+cmp+"]>0 ? node.getLeft()["+node.getLeft()+"]: node.getRight()["+node.getRight()+"]");
node=(cmp>0 ? node.getLeft() : node.getRight());
System.out.println("2:(cmp["+cmp+"]>0 ? node.getLeft()["+node.getLeft()+"]: node.getRight()["+node.getRight()+"]");
}//else
}//while
if(node == null)
//kein Knoten gefunden
return false;
//Fall 1:Knoten k ist ein Blatt, d.h. es muss nur der
//Elternknoten bestimmt werden und der Verweis auf Knoten
//k muss entfernt werden (einfachste Fall)
if(node.getLeft() == null && node.getRight() == null)
child = null;
//Fall 2:Knoten k ist ein Kindknoten, d.h. der Verweis
//vom Elternknoten auf den Kindknoten von k umzulenken
else if(node.getLeft() == null)
child = node.getRight();
else if(node.getRight() == null)
child = node.getLeft();
else
{
/*Fall 3:Knoten k ist ein inneren Knoten mit zwei
*Kinderknoten, d.h. es muss der Knoten durch den
*am weitesten links stehenden Knoten des rechten
*Teilbaums ersetzt werden, da dieser in der
*Sortierreihenfolge der nächste Knoten ist
*/
//minimales Element suchen
child = node.getRight();
tmp = node;
while(child.getLeft()!= null)
{
tmp = child;
child = child.getLeft();
}//while
child.setLeft(node.getLeft());
if(tmp != node)
{
tmp.setLeft(child.getRight());
child.setRight(tmp);
}//if
}//else
if(parent.getLeft() == node)
parent.setLeft(child);
else
parent.setRight(child);
return true;
}sieht jemand meine Fehler?
Vielen dank schonmal im voraus!
