// Binary Search Tree full program is available here: link
private BinarySearchTree ParentNode; //Parent Node of the node to delete
private boolean LeftOrRightFlag; //Deleting node is Left from parent means true, else Right means false
public void DeleteNode(int data) {
DeleteNode(this, data);
}
private void DeleteNode(BinarySearchTree T, int data) {
if(T==null) return;
if(data==T.data) { //delete root note
T.data=getMin(T.right).data;
DeleteNode(T.right, T.data);
} else {
BinarySearchTree Current = findNode(T, data);
if(Current.left==null && Current.right==null)
if(LeftOrRightFlag)
ParentNode.left=null;
else
ParentNode.right=null;
else if(Current.left==null)
if(LeftOrRightFlag)
ParentNode.left=Current.right;
else
ParentNode.right=Current.right;
else if(Current.right==null)
if(LeftOrRightFlag)
ParentNode.left=Current.left;
else
ParentNode.right=Current.left;
else {//Current node has both children
Current.data=getMin(Current.right).data;
DeleteNode(T.right, Current.data);
}
}
}
private BinarySearchTree getMin(BinarySearchTree T) {
while(T.left!=null)
T=T.left;
return T;
}
public BinarySearchTree findNode(BinarySearchTree T,int data) { //except root
if(data==T.data)
return T;
else if(data<T.data) {
ParentNode=T;
LeftOrRightFlag=true;
return findNode(T.left, data);
} else {
ParentNode=T;
LeftOrRightFlag=false;
return findNode(T.right, data);
}
}
No comments:
Post a Comment