Code:
#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node *left;
int data;
struct node *right;
};
void insert(struct node **root, int data);
void search(struct node** root, int data);
struct node * searchloc(struct node **root, int data);
void delete(struct node **root, int data);
struct node * searchparent(struct node **root, struct node *temp);
struct node * inorder(struct node *root, struct node *temp);
int main(void)
{
//printf("\n %d", SIZE);
struct node *root = NULL;
int data;
char ch;
do
{
printf("\n Enter the data\n");
scanf("%d", &data);
insert(&root, data);
printf("\n Do you want to add more elements\n");
scanf("\n%c", &ch);
}while(ch == 'y' || ch == 'Y');
printf("\n Do you want to search data");
scanf("\n %c", &ch);
while(ch == 'y' || ch == 'Y')
{
printf("\n Enter the data to search in the BST");
scanf("\n %d", &data);
search(&root, data);
printf("\n Do you want to search data");
scanf("\n %c", &ch);
}
delete(&root, 8);
return 0;
}
void delete(struct node **root, int data)
{
struct node *temp = NULL;
struct node ** r;
struct node *parent;
struct node *insuc;
r = root;
// find where is the data that is get the address
temp = searchloc(r, data);
if(temp != NULL)
printf("\n Location at which element was found is %p", temp);
else
{
printf("\n The data that you tried to delete doesnt exist in the list");
return;
}
r = root;
// get the parents address as well
parent = searchparent(*r, temp);
if(parent != NULL)
printf("\n Location at which parent was found is %p", parent);
// the location where the element has been found has no children
// simply delete the element and move ahead
if(temp->left == NULL && temp->right == NULL)
{
// set the pointer in the parent to null
if(parent->left == temp)
parent->left = NULL;
else if (parent->right == temp)
parent->right = NULL;
free(temp);
}
// the location where the element has been found has one children
// set the pointer in the parent to point to the child
if(temp->left == NULL && temp->right != NULL)
{
if(parent->left == temp)
parent->left = temp->right;
else if(parent->right == temp)
parent->right = temp->right;
free(temp);
return;
}
else if(temp->left != NULL && temp->right == NULL)
{
if(parent->left == temp)
parent->left = temp->left;
else if(parent->right == temp)
parent->right = temp->left;
free(temp);
return;
}
// the location where the element has been found has two children
// 1. Find the inorder successor
// 2. Copy its data to the node being deleted
// 3. The inorder successor will always have one or no child
// which reduces the problem to deletion of a node with one or zero child
if(temp->left != NULL && temp->right != NULL)
{
// find the location of the inorder successor
insuc = inorder(root, temp);
printf("\n Location of inorder successor is %p and its value is %d", insuc, insuc->data);
}
}
struct node * inorder(struct node **root, struct node *temp)
{
int i = 0;
if((*root) != NULL)
{
inorder((*root)->left, temp);
if(temp->data == (*root)->data)
{
printf("\n %d", (*root)->data);
++ i;
}
// next time i come here with value of i being 1 i would have got the inorder successor
else
{
if(i == 1)
{
return (*root);
}
else
printf("\n Still searching");
}
inorder((*root)->right, temp);
}
}
struct node * searchparent(struct node *root, struct node *temp)
{
if(root->left != NULL && root->left == temp)
{
return root;
}
else if(root->left != NULL)
{
searchparent(root->left, temp);
if(root->right != NULL)
searchparent(root->right, temp);
}
if(root->right != NULL && root->right == temp)
{
return root;
}
else if(root->left != NULL)
{
searchparent(root->left, temp);
if(root->right != NULL)
searchparent(root->right, temp);
}
}
struct node * searchloc(struct node **root, int data)
{
if((*root)->data == data)
{
printf("\n Data Found in the tree");
return (*root);
}
// search in the left of the root
else if((*root)->data < data)
{
if((*root)->right != NULL)
{
searchloc(&(*root)->right, data);
}
else
{
printf("\n Data not in the tree");
return NULL;
}
}
// search in the right of the root
else if((*root)->data > data)
{
if((*root)->left != NULL)
{
searchloc(&(*root)->left, data);
}
else
{
printf("\n Data not in the tree");
return NULL;
}
}
else
{
printf("\n Data does not exist in the tree");
return NULL;
}
}
void search(struct node** root, int data)
{
if((*root)->data == data)
{
printf("\n Data Found in the tree");
return;
}
// search in the left of the root
else if((*root)->data < data)
{
if((*root)->right != NULL)
{
search(&(*root)->right, data);
}
else
{
printf("\n Data not in the tree");
return;
}
}
// search in the right of the root
else if((*root)->data > data)
{
if((*root)->left != NULL)
{
search(&(*root)->left, data);
}
else
{
printf("\n Data not in the tree");
return;
}
}
else
{
printf("\n Data does not exist in the tree");
return;
}
}
void insert(struct node **root, int data)
{
struct node *temp;
// check if its the first element that i am going to add
if(*root == NULL)
{
*root = (struct node *) malloc(sizeof(struct node));
(*root)->left = NULL;
(*root)->right = NULL;
(*root)->data = data;
return;
}
// this is not the first element
// find its correct place in the tree
// data is larger than root so put in the right
else
{
if((*root)->data < data)
{
insert(&((*root)->right), data);
}
else if((*root)->data > data)
{
insert(&((*root)->left), data);
}
}
}
Originally Posted by roaan
