Posts Tagged deletion
Program for insertion and deletion in heap.
Posted by admin in C Examples on August 27th, 2009
# include <stdio.h>
int arr[100],n;
main()
{
int choice,num;
n=0;/*Represents number of nodes in the heap*/
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the number to be inserted : ");
scanf("%d",&num);
insert(num,n);
n=n+1;
break;
case 2:
printf("Enter the number to be deleted : ");
scanf("%d",&num);
del(num);
break;
case 3:
display();
break;
case 4:
exit();
default:
printf("Wrong choice\n");
}/*End of switch */
}/*End of while */
}/*End of main()*/
display()
{ int i;
if(n==0)
{
printf("Heap is empty\n");
return;
}
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
}/*End of display()*/
insert(int num,int loc)
{
int par;
while(loc>0)
{
par=(loc-1)/2;
if(num<=arr[par])
{
arr[loc]=num;
return;
}
arr[loc]=arr[par];
loc=par;
}/*End of while*/
arr[0]=num; /*assign num to the root node */
}/*End of insert()*/
del(int num)
{
int left,right,i,temp,par;
for(i=0;i<n;i++)
{
if(num==arr[i])
break;
}
if( num!=arr[i] )
{
printf("%d not found in heap\n",num);
return;
}
arr[i]=arr[n-1];
n=n-1;
par=(i-1)/2; /*find parent of node i */
if(arr[i] > arr[par])
{
insert( arr[i],i);
return;
}
left=2*i+1; /*left child of i*/
right=2*i+2; /* right child of i*/
while(right < n)
{
if( arr[i]>=arr[left] && arr[i]>=arr[right] )
return;
if( arr[right]<=arr[left] )
{
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
i=left;
}
else
{
temp=arr[i];
arr[i]=arr[right];
arr[right]=temp;
i=right;
}
left=2*i+1;
right=2*i+2;
}/*End of while*/
if( left==n-1 && arr[i]<arr[left] ) /* right==n */
{ temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
}
}/*End of del()*/
Insertion ,Deletion and Traversal in fully in-threaded Binary Search Tree
Posted by admin in C Examples on August 27th, 2009
# include <stdio.h>
# include <malloc.h>
#define infinity 9999
typedef enum { thread,link} boolean;
struct node *in_succ(struct node *p);
struct node *in_pred(struct node *p);
struct node
{
struct node *left_ptr;
boolean left;
int info;
boolean right;
struct node *right_ptr;
}*head=NULL;
main()
{
int choice,num;
insert_head();
while(1)
{
printf("\n");
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Inorder Traversal\n");
printf("4.Preorder Traversal\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the number to be inserted : ");
scanf("%d",&num);
insert(num);
break;
case 2:
printf("Enter the number to be deleted : ");
scanf("%d",&num);
del(num);
break;
case 3:
inorder();
break;
case 4:
preorder();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch */
}/*End of while */
}/*End of main()*/
insert_head()
{
struct node *tmp;
head=(struct node *)malloc(sizeof(struct node));
head->info= infinity;
head->left=thread;
head->left_ptr=head;
head->right=link;
head->right_ptr=head;
}/*End of insert_head()*/
find(int item,struct node **par,struct node **loc)
{
struct node *ptr,*ptrsave;
if(head->left_ptr==head) /* If tree is empty*/
{
*loc=NULL;
*par=head;
return;
}
if(item==head->left_ptr->info) /* item is at head->left_ptr */
{
*loc=head->left_ptr;
*par=head;
return;
}
ptr=head->left_ptr;
while(ptr!=head)
{
ptrsave=ptr;
if( item < ptr->info )
{
if(ptr->left==link)
ptr=ptr->left_ptr;
else
break;
}
else
if(item > ptr->info )
{
if(ptr->right==link)
ptr=ptr->right_ptr;
else
break;
}
if(item==ptr->info)
{
*loc=ptr;
*par=ptrsave;
return;
}
}/*End of while*/
*loc=NULL; /*item not found*/
*par=ptrsave;
}/*End of find()*/
insert(int item)
{
struct node *tmp,*parent,*location;
find(item,&parent,&location);
if(location!=NULL)
{
printf("Item already present");
return;
}
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=item;
tmp->left=thread;
tmp->right=thread;
if(parent==head) /*tree is empty*/
{
head->left=link;
head->left_ptr=tmp;
tmp->left_ptr=head;
tmp->right_ptr=head;
}
else
if( item < parent->info )
{
tmp->left_ptr=parent->left_ptr;
tmp->right_ptr=parent;
parent->left=link;
parent->left_ptr=tmp;
}
else
{
tmp->left_ptr=parent;
tmp->right_ptr=parent->right_ptr;
parent->right=link;
parent->right_ptr=tmp;
}
}/*End of insert()*/
del(int item)
{
struct node *parent,*location;
if(head==NULL)
{
printf("Tree empty");
return;
}
find(item,&parent,&location);
if(location==NULL)
{
printf("Item not present in tree");
return;
}
if(location->left==thread && location->right==thread)
case_a(parent,location);
if(location->left==link && location->right==thread)
case_b(parent,location);
if(location->left==thread && location->right==link)
case_b(parent,location);
if(location->left==link && location->right==link )
case_c(parent,location);
}/*End of del()*/
case_a(struct node *par,struct node *loc )
{
if(par==head) /*item to be deleted is first node*/
{
head->left=thread;
head->left_ptr=head;
}
else
if(loc==par->left_ptr)
{
par->left=thread;
par->left_ptr=loc->left_ptr;
}
else
{
par->right=thread;
par->right_ptr=loc->right_ptr;
}
free(loc);
}/*End of case_a()*/
case_b(struct node *par,struct node *loc)
{
struct node *child,*s,*p;
/*Initialize child*/
if(loc->left==link) /*item to be deleted has left_ptr */
child=loc->left_ptr;
else /*item to be deleted has right_ptr */
child=loc->right_ptr;
if(par==head ) /*Item to be deleted is first node*/
head->left_ptr=child; //see this one
else
if( loc==par->left_ptr) /*item is left_ptr of its parent*/
par->left_ptr=child;
else /*item is right_ptr of its parent*/
par->right_ptr=child;
s=in_succ(loc);
p=in_pred(loc);
if(loc->right==link) /*if loc has right subtree*/
s->left_ptr=p;
else /*if loc has left subtree */
{
if( loc->left==link)
p->right_ptr=s;
}
free(loc);
}/*End of case_b()*/
case_c(struct node *par,struct node *loc)
{
struct node *ptr,*ptrsave,*suc,*parsuc,*s,*p;
/*Find inorder successor and its parent*/
ptrsave=loc;
ptr=loc->right_ptr;
while(ptr->left==link)
{
ptrsave=ptr;
ptr=ptr->left_ptr;
}
suc=ptr;
parsuc=ptrsave;
loc->info=suc->info;
if(suc->left==thread && suc->right==thread)
case_a(parsuc,suc);
else
case_b(parsuc,suc);
}/*End of case_c()*/
struct node *in_succ(struct node *ptr)
{
struct node *succ;
if(ptr->right==thread)
succ=ptr->right_ptr;
else
{
ptr=ptr->right_ptr;
while(ptr->left==link)
ptr=ptr->left_ptr;
succ=ptr;
}
return succ;
}/*End of in_succ()*/
struct node *in_pred(struct node *ptr)
{
struct node *pred;
if(ptr->left==thread)
pred=ptr->left_ptr;
else
{
ptr=ptr->left_ptr;
while(ptr->right==link)
ptr=ptr->right_ptr;
pred=ptr;
}
return pred;
}/*End of in_pred()*/
inorder()
{
struct node *ptr;
if(head->left_ptr==head)
{
printf("Tree is empty");
return;
}
ptr=head->left_ptr;
/*Find the leftmost node and traverse it */
while(ptr->left==link)
ptr=ptr->left_ptr;
printf("%d ",ptr->info);
while( 1 )
{
ptr=in_succ(ptr);
if(ptr==head) /*If last node reached */
break;
printf("%d ",ptr->info);
} /*End of while*/
}/*End of inorder()*/
preorder()
{
struct node *ptr;
if(head->left_ptr==head)
{
printf("Tree is empty");
return;
}
ptr=head->left_ptr;
while( ptr != head )
{
printf("%d ",ptr->info);
if( ptr->left==link )
ptr=ptr->left_ptr;
else
if(ptr->right_ptr==link)
ptr=ptr->right_ptr;
else
{
while( ptr!=head && ptr->right==thread )
ptr=ptr->right_ptr;
if(ptr!=head )
ptr=ptr->right_ptr;
}
}/*End of while*/
}/*End of preorder()*/
Program to implement threaded binary tree
Posted by admin in C Examples on June 24th, 2009
/* Program to implement threaded binary tree */
#include "alloc.h"
enum boolean
{
false = 0 ,
true = 1 ,
} ;
struct thtree
{
enum boolean left ;
struct thtree *leftchild ;
int data ;
struct thtree *rightchild ;
enum boolen right ;
} ;
main( )
{
struct thtree *th_head ;
th_head = NULL ;/* empty tree */
insert ( &th_head, 11 ) ;
insert ( &th_head, 9 ) ;
insert ( &th_head, 13 ) ;
insert ( &th_head, 8 ) ;
insert ( &th_head, 10 ) ;
insert ( &th_head, 12 ) ;
insert ( &th_head, 14 ) ;
insert ( &th_head, 15 ) ;
insert ( &th_head, 7 ) ;
clrscr( ) ;
printf ( "Threaded binary tree before deletion: " ) ;
inorder ( th_head ) ;
delete ( &th_head, 10 ) ;
printf ( "\nThreaded binary tree after deletion: " ) ;
inorder ( th_head ) ;
delete ( &th_head, 14 ) ;
printf ( "\nThreaded binary tree after deletion: " ) ;
inorder ( th_head ) ;
delete ( &th_head, 8 ) ;
printf ( "\nThreaded binary tree after deletion: " ) ;
inorder ( th_head ) ;
delete ( &th_head, 13 ) ;
printf ( "\nThreaded binary tree after deletion: " ) ;
inorder ( th_head ) ;
}
/* inserts a node in a threaded binary tree */
insert ( struct thtree **s, int num )
{
struct thtree *head = *s , *p, *z ;
/* allocating a new node */
z = malloc ( sizeof ( struct thtree ) ) ;
z -> left = true ; /* indicates a thread */
z -> data = num ; /* assign new data */
z -> right = true ; /* indicates a thread */
/* if tree is empty */
if ( *s == NULL )
{
head = malloc ( sizeof ( struct thtree ) ) ;
/* the entire tree is treated as a left subtree of the head node */
head -> left = false ;
head -> leftchild = z ; /* z becomes leftchild of the head node */
head -> data = -9999 ; /* no data */
head -> rightchild = head ; /* right link will always be pointing to itself */
head -> right = false ;
*s = head ;
z -> leftchild = head ; /* left thread to head */
z -> rightchild = head ; /* right thread to head */
}
else /* if tree is non-empty */
{
p = head -> leftchild ;
/* traverse till the thread is found attached to the head */
while ( p != head )
{
if ( p -> data > num )
{
if ( p -> left != true ) /* checking for a thread */
p = p -> leftchild ;
else
{
z -> leftchild = p -> leftchild ;
p -> leftchild = z ;
p -> left = false ; /* indicates a link */
z -> right = true ;
z -> rightchild = p ;
return ;
}
}
else
{
if ( p -> data < num )
{
if ( p -> right != true )
p = p -> rightchild ;
else
{
z -> rightchild = p -> rightchild ;
p -> rightchild = z ;
p -> right = false ; /* indicates a link */
z -> left = true ;
z -> leftchild = p ;
return ;
}
}
}
}
}
}
/* deletes a node from the binary search tree */
delete ( struct thtree **root, int num )
{
int found ;
struct thtree *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 -> left == false && x -> right == false )
{
parent = x ;
xsucc = x -> rightchild ;
while ( xsucc -> left == false )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}
x -> data = xsucc -> data ;
x = xsucc ;
}
/* if the node to be deleted has no child */
if ( x -> left == true && x -> right == true )
{
if ( parent -> rightchild == x )
{
parent -> right = true ;
parent -> rightchild = x -> rightchild ;
}
else
{
parent -> left = true ;
parent -> leftchild = x -> leftchild ;
}
free ( x ) ;
return ;
}
/* if the node to be deleted has only rightchild */
if ( x -> left == true && x -> right == false )
{
if ( parent -> leftchild == x )
{
parent -> leftchild = x -> rightchild ;
x -> rightchild -> leftchild = x -> leftchild ;
}
else
{
parent -> rightchild = x -> rightchild ;
x -> rightchild -> leftchild = parent ;
}
free ( x ) ;
return ;
}
/* if the node to be deleted has only left child */
if ( x -> left == false && x -> right == true )
{
if ( parent -> leftchild == x )
{
parent -> leftchild = x -> leftchild ;
x -> leftchild -> rightchild = parent ;
}
else
{
parent -> rightchild = x -> leftchild ;
x -> leftchild -> rightchild = x -> rightchild ;
}
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 thtree **root, int num, struct thtree **par, struct thtree **x, int *found )
{
struct thtree *q ;
q = ( *root ) -> leftchild ;
*found = false ;
*par = NULL ;
while ( q != root )
{
/* 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 ;
}
}
}
/* traverses the threaded binary tree in inorder */
inorder ( struct thtree *root )
{
struct thtree *p ;
p = root -> leftchild ;
while ( p != root )
{
while ( p -> left == false )
p = p -> leftchild ;
printf ( "%d ", p -> data ) ;
while ( p -> right == true )
{
p = p -> rightchild ;
if ( p == root )
break ;
printf ( "%d ", p -> data ) ;
}
p = p -> rightchild ;
}
}
Deleting a node in a binary tree
Posted by admin in C Examples on June 24th, 2009
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 ;
}
-
FeedCount
Recent Comments