-1
Warum kann ich den gewünschten Knoten nicht löschen? Wenn ich beispielsweise einen Baum mit Einträgen in dieser Reihenfolge 1,2,3,4,5 konstruiere und meine Löschmethode zum Löschen von 3 verwende, dann werden die Knoten, die 3 und weniger enthalten, statt nur 3 gelöscht, und ich werde 4,5 erhalten wenn ich wieder alle Knoten in preorder.Please help.Löschen in binärer Suchbaum in Java
importieren java.util.Scanner;
Klasse TNODE {
protected int data;
protected tnode left,right;
public tnode(){
data=0;
right=left=null;
}
public tnode(int v){
data=v;
right=left=null;
}
public int getdata(){
return data;
}
public tnode getleft(){
return left;
}
public tnode getright(){
return right;
}
} Klasse btree {
protected tnode root;
public btree(){
root=null;
}
public boolean isEmpty(){
return root==null;
}
public void insert(int val){
root=insert(root,val);
}
private tnode insert(tnode r,int val){
if(r==null){
r=new tnode(val);
}
else{
if(val>r.getdata()){
r.right=insert(r.right,val);
}
else{
r.left=insert(r.left,val);
}
}
return r;
}
public void preorder(){
preorder(root);
}
private void preorder(tnode r){
if(r!=null){
System.out.print(r.getdata()+" ");
preorder(r.getleft());
preorder(r.getright());
}
}
public int min(){
return min(root);
}
public int min(tnode r){
if(r.left==null){
return r.getdata();
}
else{
return min(r.left);
}
}
public void delete(int val){
root=delete(root,val);
}
private tnode delete(tnode r,int val){
if(r==null){
return null;
}
else if(val>r.getdata()){
r=delete(r.right,val);
}
else if(val<r.getdata()){
r=delete(r.left,val);
}
else{// when r.data=value
//if node has both children
if(r.left!=null && r.right!=null){
tnode temp=r;
//get the minimum value in right sub tree
int min_right=min(temp.right);
//replace this with the node to be deleted
r.data=min_right;
//delete this node
r=delete(r.right,min_right);
}
//if has left child
else if(r.left!=null){
r=r.left;
}
//if has right child
else if(r.right!=null){
r=r.right;
}
else{
//if has no child
r=null;
}
}
return r;
}
}