C++ Program for deletion in Threaded Binary Tree
Deletion in Threaded Binary Tree
We have seen insertion in and displaying of Threaded binary tree (click here -> javascript:nicTemp(); )
Now lets see deletion of threaded binary tree;
For deletion we have to consider three cases:
CASE-1 : Node to be deleted is a leaf node.
CASE-2 : Node to be deleted has only one child.
CASE-3 : Node to be deleted has two children
Lets discuss each case in detail
CASE-1 : Node to be deleted is a leaf node
Again we have two cases :
CASE-A If the leaf Node is to be deleted is left child of its parent then after deletion, left pointer of parent should become a thread pointing to its predecessor of the parent Node after deletion.
CASE-B If the leaf Node to be deleted is right child of its parent then after deletion, right pointer of parent should become a thread pointing to its successor.
C++ Program for case-1 deletion
struct Node* Case_1(struct Node* root , struct Node* par ,struct Node* ptr )
{
// If Node to be deleted is root
if (par == NULL)
root = NULL;
// If Node to be deleted is left of its parent
else if (ptr == par->left) {
par->lthread = true;
par->left = ptr->left;
}
//If Node to be deleted is right of its parent
else {
par->rthread = true;
par->right = ptr->right;
}
// Free memory and return new root
free(ptr);
return root;
{
// If Node to be deleted is root
if (par == NULL)
root = NULL;
// If Node to be deleted is left of its parent
else if (ptr == par->left) {
par->lthread = true;
par->left = ptr->left;
}
//If Node to be deleted is right of its parent
else {
par->rthread = true;
par->right = ptr->right;
}
// Free memory and return new root
free(ptr);
return root;
}
CASE-2 Node to be deleted has only one child
If Node to be deleted has left subtree, then after deletion right thread of its predecessor should point to its successor.
If Node to be deleted has right subtree, then after deletion left thread of its successor should point to its prredecessor.
C++ program for case-2 deletion
struct Node* Case_2( struct Node* root, struct Node* par, struct Node* ptr )
{
struct Node* child;
// Initialize child
//Node to be deleted has left child.
if (ptr->lthread == false)
child = ptr->left;
// Node to be deleted has right child.
else
child = ptr->right;
// Node to be deleted is root Node.
if (par == NULL)
root = child;
// Node is left child of its parent.
else if (ptr == par->left)
par->left = child;
//Node is right child of its parent
else
par->right = child;
// Find successor and predecessor
Node* s = inordersuccessor (ptr);
Node* p = inorderpedecessor (ptr);
// If ptr has left subtree.
if (ptr->lthread == false)
p->right = s;
// If ptr has right subtree.
else {
if (ptr->rthread == false)
s->left = p;
}
free(ptr);
return root;
};
{
struct Node* child;
// Initialize child
//Node to be deleted has left child.
if (ptr->lthread == false)
child = ptr->left;
// Node to be deleted has right child.
else
child = ptr->right;
// Node to be deleted is root Node.
if (par == NULL)
root = child;
// Node is left child of its parent.
else if (ptr == par->left)
par->left = child;
//Node is right child of its parent
else
par->right = child;
// Find successor and predecessor
Node* s = inordersuccessor (ptr);
Node* p = inorderpedecessor (ptr);
// If ptr has left subtree.
if (ptr->lthread == false)
p->right = s;
// If ptr has right subtree.
else {
if (ptr->rthread == false)
s->left = p;
}
free(ptr);
return root;
};
CASE-3 Node to be deleted has 2 Children
We find inorder successor of Node ptr (Node to be deleted) and then copy the information of this successor into Node ptr. After this inorder successor Node is deleted using either Case A or Case B.
C++ Program for Case-3 deletion
struct Node* Case_3(struct Node* root, struct Node* par, struct Node* ptr){
// Find inorder successor and its parent.
struct Node* parsucc = ptr;
struct Node* succ = ptr->right;
// Find leftmost child of successor
while (succ->left != NULL) {
parsucc = succ;
succ = succ->left;
}
ptr->data = succ->data;
if (succ->lthread == true && succ->rthread == true)
root = Case_1(root, parsucc, succ);
else
root = Case_2(root, parsucc, succ);
return root;
}
Now , first we have to find the node in the tree and then different cases are applied to the node to be deleted
C++ program for finding key node and then calling different function to delete that node
struct Node* delete_Node( struct Node *root, int key)
{
struct Node *parent= NULL;
struct Node *ptr= root;
//set true if key is found
bool found = false;
//search key in tree
while( ptr != NULL)
{
if(ptr -> data == key )
{
found = true;
break;
}
parent = ptr;
if ( key < ptr -> data)
{
if(ptr -> lthread == false)
ptr = ptr -> left;
else
break;
}
else
{
if( ptr -> rthread == false)
ptr = ptr -> right;
else
break;
}
}
if( found == false)
cout<<"Data is not present in the tree\n";
else{
if(ptr -> lthread == false && ptr -> rthread == false )
root= Case_3(root, parent, ptr);
else if(ptr -> lthread == true && ptr -> rthread == false )
root= Case_2(root, parent, ptr);
else if(ptr -> lthread == false && ptr -> rthread == true )
root= Case_2(root, parent, ptr);
else if(ptr -> lthread == true && ptr -> rthread == true )
root= Case_1(root, parent, ptr);
}
}
{
struct Node *parent= NULL;
struct Node *ptr= root;
//set true if key is found
bool found = false;
//search key in tree
while( ptr != NULL)
{
if(ptr -> data == key )
{
found = true;
break;
}
parent = ptr;
if ( key < ptr -> data)
{
if(ptr -> lthread == false)
ptr = ptr -> left;
else
break;
}
else
{
if( ptr -> rthread == false)
ptr = ptr -> right;
else
break;
}
}
if( found == false)
cout<<"Data is not present in the tree\n";
else{
if(ptr -> lthread == false && ptr -> rthread == false )
root= Case_3(root, parent, ptr);
else if(ptr -> lthread == true && ptr -> rthread == false )
root= Case_2(root, parent, ptr);
else if(ptr -> lthread == false && ptr -> rthread == true )
root= Case_2(root, parent, ptr);
else if(ptr -> lthread == true && ptr -> rthread == true )
root= Case_1(root, parent, ptr);
}
}
Comments