Deleting a node in a binary tree

In addition to techniques for inserting data in a binary tree and traversing the tree, practical examples call for deleting data from the binary tree. Assuming that we will pass the specified data item that we wish to delete to the delete( ) function, there are four possible cases that we need to consider:

  • No node in the tree contains the specified data.
  • The node containing the data has no children.
  • The node containing the data has exactly one child.
  • The node containing the data has two children.

/* Program to to delete a node form a binary search tree */

 #include "alloc.h"

 #define TRUE 1

 #define FALSE 0

 struct btreenode

 {

struct btreenode *leftchild ;

int data ;

struct btreenode *rightchild ;

 } ;

 main( )

 {

struct btreenode *bt ;

int req, i = 0, num, a[ ]= { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;

bt = NULL ;/* empty tree */

clrscr( ) ;

while ( i <= 8 )

{

insert ( &bt, a[i] ) ;

i++ ;

}

clrscr( ) ;

printf ( "Binary tree before deletion: " ) ;

inorder ( bt ) ;

delete ( &bt, 10 ) ;

printf ( "\nBinary tree after deletion: " ) ;

inorder ( bt ) ;

delete ( &bt, 14 ) ;

printf ( "\nBinary tree after deletion: " ) ;

inorder ( bt ) ;

delete ( &bt, 8 ) ;

printf ( "\nBinary tree after deletion: " ) ;

inorder ( bt ) ;

delete ( &bt, 13 ) ;

printf ( "\nBinary tree after deletion: " ) ;

inorder ( bt ) ;

 }

 /* inserts a new node in a binary search tree */

 insert ( struct btreenode **sr, int num )

 {

if ( *sr == NULL )

{

*sr = malloc ( sizeof ( struct btreenode ) ) ;

( *sr ) -> leftchild = NULL ;

( *sr ) -> data = num ;

( *sr ) -> rightchild = NULL ;

return ;

}

else /* search the node to which new node will be attached */

{

/* if new data is less, traverse to left */

if ( num < ( *sr ) -> data )

insert ( &( ( *sr ) -> leftchild ), num ) ;

else

/* else traverse to right */

insert ( &( ( *sr ) -> rightchild ), num ) ;

}

return ;

 }

 /* deletes a node from the binary search tree */

 delete ( struct btreenode **root, int num )

 {

int found ;

struct btreenode *parent, *x, *xsucc ;

/* if tree is empty */

if ( *root == NULL )

{

printf ( "\nTree is empty" ) ;

return ;

}

parent = x = NULL ;

/* call to search function to find the node to be deleted */

search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */

if ( found == FALSE )

{

printf ( "\nData to be deleted, not found" ) ;

return ;

}

/* if the node to be deleted has two children */

if ( x -> leftchild != NULL && x -> rightchild != NULL)

{

parent = x ;

xsucc = x -> rightchild ;

while ( xsucc -> leftchild != NULL )

{

parent = xsucc ;

xsucc = xsucc -> leftchild ;

}

x -> data = xsucc -> data ;

x = xsucc ;

}

/* if the node to be deleted has no child */

if ( x -> leftchild == NULL && x -> rightchild == NULL )

{

if ( parent -> rightchild == x )

parent -> rightchild = NULL ;

else

parent -> leftchild = NULL ;

free ( x ) ;

return ;

}

/* if the node to be deleted has only rightchild */

if ( x -> leftchild == NULL && x -> rightchild != NULL )

{

if ( parent -> leftchild == x )

parent -> leftchild = x -> rightchild ;

else

parent -> rightchild = x -> rightchild ;

free ( x ) ;

return ;

}

/* if the node to be deleted has only left child */

if ( x -> leftchild != NULL && x -> rightchild == NULL )

{

if ( parent -> leftchild == x )

parent -> leftchild = x -> leftchild ;

else

parent -> rightchild = x -> leftchild ;

free ( x ) ;

return ;

  }

 }

 /* returns the address of the node to be deleted, address of its parent and whether the node is found or not */

search ( struct btreenode **root, int num, struct btreenode **par, struct btreenode **x, int *found )

 {

struct btreenode *q ;

q = *root ;

*found = FALSE ;

*par = NULL ;

while ( q != NULL )

{

/* if the node to be deleted is found */

if ( q -> data == num )

{

*found = TRUE ;

*x = q ;

return ;

}

if ( q -> data > num )

{

*par = q ;

q = q -> leftchild ;

}

else

{

*par = q ;

q = q -> rightchild ;

}

}

 }

 /* traverse a binary search tree in a LDR (Left-Data-Right) fashion */

 inorder ( struct btreenode *sr )

 {

if ( sr != NULL )

{

inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path has already been traversed */

printf ( "%d ", sr -> data ) ;

inorder ( sr -> rightchild ) ;

}

else

return ;

 }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s