Binary Search Tree: Deleting node
#include<stdio.h>
#include<stdlib.h>
struct BST
{
int
data;
struct
BST *lchild, *rchild;
};
typedef struct BST * NODE;
NODE get_node()
{
NODE
temp;
temp
= (NODE) malloc(sizeof(struct BST));
temp->lchild
= NULL;
temp->rchild
= NULL;
return
temp;
}
void insert(NODE root, NODE newnode)
{
if
(newnode->data < root->data)
{
if
(root->lchild == NULL)
root->lchild
= newnode;
else
insert(root->lchild,
newnode);
}
if
(newnode->data > root->data)
{
if
(root->rchild == NULL)
root->rchild
= newnode;
else
insert(root->rchild,
newnode);
}
}
void inorder(NODE root)
{
if(root
!= NULL)
{
inorder(root->lchild);
printf("%d
", root->data);
inorder(root->rchild);
}
}
NODE delete_item(NODE root, int item)
{
NODE cur, parent, succ,
psucc, child;
if(root == NULL)
{
printf("\nTree
is empty. Nothing to delete");
return NULL;
}
/*Obtain
the node to be deleted and its parent*/
parent = NULL;
cur = root;
while(cur!=NULL)
{
if(item ==
cur->data)
break;
parent = cur;
if(item <
cur->data)
cur
= cur->lchild;
else if(item >
cur->data)
cur
= cur->rchild;
}
if(cur == NULL)
{
printf("\nItem
not found");
return root;
}
/*If item is
found then delete it: node to be deleted is cur*/
if(cur->lchild
==NULL) /*if cur node's left subtree is empty , obtain non empty right subtree
*/
child =
cur->rchild;
else if(cur->rchild ==NULL) /*if cur
node's left subtree is empty , obtain non empty right subtree */
child =
cur->lchild;
else
{
/*Find the inorder successor and its parent*/
psucc = cur;
succ =
cur->rchild;
/*Find
the minimum node (inorder successor) in the right subtree of cur node*/
while(succ->lchild
!= NULL)
{
psucc
= succ;
succ
= succ->lchild;
}
if(cur == psucc)
succ->lchild
= cur->lchild;
else
{
succ->lchild = cur->lchild; /* attach left
of node to be deleted(cur) to the left of successor */
psucc->lchild = succ->rchild; /* attach
right of successor to the left of parent of successor*/
succ->rchild = cur->rchild; /*attach
right of node to be deleted(cur) to the right of successor*/
}
child = succ;
printf("\nsuccessor
data = %d", child->data);
}
if(parent == NULL) /*if parent
does not exist return child as root*/
return child;
if(parent->lchild == cur)
parent->lchild = child;
else
parent->rchild =
child;
free(cur);
return
root;
}
void main()
{
int val, i,n, item;
NODE
root = NULL, newnode, del;
printf("\nEnter the
number of elements: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
newnode
= get_node();
printf("\nEnter
The node value: ");
scanf("%d",
&val);
newnode->data =
val;
if
(root == NULL)
root
= newnode;
else
insert(root,
newnode);
}
printf("\nInorder display before
deletion: ");
inorder(root);
printf("\nEnter the
Item to be deleted: ");
scanf("%d", &item);
del = delete_item(root, item);
printf("\nInorder
display after deletion: ");
inorder(del);
}
Output1:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39 45 54
55 56
61 78
80
Enter the Item to be deleted: 78
Inorder display after deletion: 39 45 54
55 56
61 80
Output2:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39 45 54
55 56
61 78
80
Enter the Item to be deleted: 54
Inorder display after deletion: 39 45 55
56 61
78 80
Output3:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39 45 54
55 56
61 78
80
Enter the Item to be deleted: 45
Inorder display after deletion: 39 54 55
56 61
78 80
Output4:
Enter the number of elements: 9
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 65
Enter The node value: 80
Inorder display before deletion: 39 45 54
55 56
61 65
78 80
Enter the Item to be deleted: 56
successor data = 61
Inorder display after deletion: 39 45 54
55 61
65 78
80
