#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
/* return the (unchanged) node pointer */
return node;
}
}
struct node* search(struct node* tmp, struct node** parent,struct node* item)
{
struct node* root;
root=tmp;
if(!root)
{
//*parent=NULL;
return NULL;
}
if(root->data==item->data)
{
return root;
}
*parent=root;
if(item->data<=root->data)
{
return search(root->left,parent,item);
}
else
{
return search(root->right,parent,item);
}
}
void deletes(struct node* root,struct node* srch)
{
struct node* parent;
struct node* succ=NULL;
if(!root)
return;
parent=NULL;
struct node* x=search(root,&parent,srch);
/* if the node to be deleted has no child */
if(x->left==NULL && x->right==NULL)
{
if(parent->left==x)
parent->left=NULL;
else
parent->right=NULL;
free(x);
return;
}
/* if the node to be deleted has only rightchild */
if (x->left == NULL && x->right!= NULL )
{
if ( parent->left == x )
parent->left = x->right ;
else
parent->right= x->right;
free ( x ) ;
return ;
}
/* if the node to be deleted has only left child */
if (x->left != NULL && x->right== NULL )
{
if ( parent->left == x )
parent->left= x->left ;
else
parent->right = x->left ;
free ( x ) ;
return ;
}
/* if the node to be deleted has two children */
if(x->left!=NULL && x->right!=NULL)
{
parent=x;
succ=x->right;
while(succ->left!=NULL)
{
parent=succ;
succ=succ->left;
}
x->data=succ->data;
x=succ;
free(x);//free(succ).....problem Might be here I dont Know why
}
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);
struct node* parent= NULL;
root=search(root,&parent,root->left->right);
printf(" %d %d ", root->data, parent->data);
deletes(root,root->left->right);
printInorder(root);
getchar();
return 0;
}
