C# OOP: Binary Search Tree

Delete node from BS 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 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 deleted.

Delete a node that has two  children.  

 2. The target node has only one or zero child 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.

///C# code to delete a node from the tree

public void delete(TreeNode Tree,int Tar)
{

TreeNode Min,Temp;
if(Tree==null) {return;}

else if(Tar<Tree.data) delete(Tree.left,Tar);//look in the left
else if(Tar>Tree.data) delete(Tree.right, Tar);//look in the right
else{ //found node to delete

   if(Tree.left!=null && Tree.right!=null) //two children
   {
    Min=findmin(Tree.right);
    Tree.data=Min.data;
    delete(Tree.right,Tree.data);

}

   else{ //one or zero child

     if(Tree.left==null)
    {
     if(Tree.parent==null) Root=Tree.right; //The root node is to be deleted.
     else{
     if(Tree.right!=null){
     Tree.right.parent=Tree.parent;
    }

  if(Tree==Tree.parent.left)
     Tree.parent.left=Tree.right;
  else Tree.parent.right=Tree.right;
  }

}
   else if(Tree.right==null)
    {
     if(Tree.parent==null) Root=Tree.left;

      else{

       Tree.left.parent=Tree.parent;
       if(Tree==Tree.parent.left)
          Tree.parent.left=Tree.left;
       else Tree.parent.right=Tree.left;
               }
        }
 


    }

  }

}





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.