Step 4: Delete a node of the binary search tree
Deleting a node from the binary search tree is a more complicate process. To delete a node there are two important things to condition:
1. The target node has two children nodes: To delete a node that has two children node, you need to replace the data value of the node with the data value of the smallest node of its right child node. Then the smallest node used in replacement will be delete.
2. The target node has only one or zero child node. We will need a temporary pointer to point to the node. If the node to be deleted has only right child node(Its left child is empty), we let the node takes its right child node's address, otherwise we let the node takes its left child node. This process also can be applied to the node that has zero child. The temporary pointer is deleted after this deletion process.
//Delete node
template <class Type>
Node<Type> *BSTree<Type>::Delete(Node<Type> **T,const Type Tar){
Node<Type> *Min,*Temp;
if((*T)==NULL) return NULL;
else if(Tar<(*T)>data) {return Delete(&(*T)>pLeft,Tar); }//look in the left
else if(Tar>(*T)>data) return Delete(&(*T)>pRight, Tar);//look in the right
else{ //found node to delete
if((*T)>pLeft && (*T)>pRight) //two children
{
Min=findmin((*T)>pRight);
(*T)>data=Min>data;
(*T)>pRight=Delete(&(*T)>pRight,(*T)>data);
}
else{ //one or zero child
Temp=*T;
if((*T)>pLeft==NULL) {(*T)=(*T)>pRight; }
else if((*T)>pRight==NULL) {(*T)=(*T)>pLeft;}
delete(Temp);
}
return *T;
}
}

This website intents to provide free and high quality tutorials, examples, exercises and solutions, questions and answers of programming and scripting languages:
C, C++, C#, Java, VB.NET, Python, VBA,PHP & Mysql, SQL, JSP, ASP.NET,HTML, CSS, JQuery, JavaScript and other applications such as MS Excel, MS Access, and MS Word. However, we don't guarantee all things of the web are accurate. If you find any error, please report it then we will take actions to correct it as soon as possible.