C++ tutorial: structure-Delete node from the tree


C++ Structure Building a Binary Search Tree

Step 4: Delete a node of the tree

Deleting a node from the tree is a more complicate process. To delete a node there are two important things to consider:

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 deleted.

Delete a node that has two  children.  

 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(set to NULL value) after this deletion process.

//Delete node

  ListElem *Delete(ListElem **T, int Tar){
  ListElem *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;}

  Temp=NULL;

 }


return *T;
}


}




Comments




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.