#include
#include
struct node{
int val;
struct node *left;
struct node *right;
};
void insert(struct node**,int);
void insert_init(struct node**);
void inorder(struct node**);
void preorder(struct node**);
void postorder(struct node**);
void search_init(struct node**,struct node **,struct node **);
void search(struct node **,int,struct node**,struct node **);
void delete_init(struct node **,struct node**,struct node **);
void delete(struct node **,struct node **,struct node**);
int main()
{
struct node *root=NULL;
struct node *parent=NULL;
struct node *curnode=NULL;
int opt=0;
while(1){
printf("\n Select an option \n 1.Insert 2.Inorder 3. Preorder 4. Postorder 5.Seatch 6.delete 7.Exit\n");
scanf("%d",&opt);
switch(opt){
case 1:{ insert_init(&root);break; }
case 2:{ printf("\nInorder Traversal\n"); inorder(&root);break; }
case 3:{ printf("\nPreorder Traversal\n");preorder(&root);break; }
case 4:{ printf("\nPostorder Traversal\n");postorder(&root);break; }
case 5:{ search_init(&root,&parent,&curnode);break; }
case 6:{ delete_init(&root,&parent,&curnode);break; }
case 7:{ exit(0);}
}
}
}
void insert_init(struct node **root) //function toread insert value
{ //input: address of root
int val;
printf("Enter an integer value\n");
scanf("%d",&val);
insert(root,val);
}
void insert(struct node **root,int val) //function for insert
{ //input address of root and input value
if(*root == NULL){
*root=(struct node *)malloc(sizeof(struct node));
(*root)->val=val;
(*root)->left=NULL;
(*root)->right=NULL;
return;
}
if((*root)->val==val){
printf("\nValue Already exists in the tree\n");
return;
}
if((*root)->val > val)
insert(&(*root)->left,val);
else
insert(&(*root)->right,val);
}
void inorder(struct node **root) //function to perform inorder traversal
{ // input to function ,address of root
if(*root == NULL)return;
inorder(&(*root)->left);
printf(" %d",(*root)->val);
inorder(&(*root)->right);
}
void preorder(struct node **root) //function to perform preorder traversal
{
if(*root == NULL)return;
printf(" %d",(*root)->val);
preorder(&(*root)->left);
preorder(&(*root)->right);
}
void postorder(struct node **root) //function to perform postorder traversal
{
if(*root == NULL)return;
preorder(&(*root)->left);
preorder(&(*root)->right);
printf(" %d",(*root)->val);
}
void search_init(struct node **root,struct node **parent,struct node **curnode)
{
int searchitem;
*parent==NULL;
printf("Enter the search item\n");
scanf("%d",&searchitem);
search(root,searchitem,parent,curnode);
}
void search(struct node **root,int searchitem,struct node **parent,struct node **curnode) //function to perform search operation
{ //inputs: root address, search item parent
if(*root == NULL) {
printf("\nItem not Found\n");
*curnode=*root;
return;
}
if(searchitem == (*root)->val) {
printf("\nItem found in the tree\n");
*curnode=*root;
return;
}
*parent=*root;
if(searchitem>(*root)->val) {
search(&(*root)->right,searchitem,parent,curnode);
} else {
search(&(*root)->left,searchitem,parent,curnode);
}
}
void delete_init(struct node **root,struct node **parent,struct node **curnode) //function to read delete item
{
int item;
struct node *temp;
printf("\n Enter the item to delete");
scanf("%d",&item);
search(root,item,parent,curnode);
if(curnode==NULL)return;
delete(root,curnode,parent);
}
void delete(struct node **root,struct node **nodetodel,struct node **parent) //function to delete a node
{
struct node *tempparent;
struct node *swapnode;
if(((*nodetodel)->right == NULL )&&((*nodetodel)->left == NULL)) {
if(*parent==NULL) {
*root=NULL;
free(*nodetodel);
}else {
if((*parent)->val > (*nodetodel)->val) {
(*parent)->left=NULL;
}else {
(*parent)->right=NULL;
}
free(*nodetodel);
}
return;
}
if((*nodetodel)->right!=NULL) {
swapnode=*nodetodel;
tempparent=swapnode;
swapnode=swapnode->right;
while(swapnode->left != NULL) { //traverse to leftmost node
tempparent=swapnode;
swapnode=swapnode->left;
}
(*nodetodel)->val=swapnode->val;
*parent=tempparent;
if( (*parent)->val > swapnode->val ) {
(*parent)->left=NULL;
} else {
(*parent)->right=NULL;
}
if(swapnode->right != NULL)
(*parent)->left=swapnode->right; //new condition(for debug)
free(swapnode);
return;
}
if((*nodetodel)->left != NULL) {
swapnode=*nodetodel;
tempparent=swapnode;
swapnode=swapnode->left;
while(swapnode->right != NULL) { //traverse to right most node
tempparent=swapnode;
swapnode=swapnode->right;
}
(*nodetodel)->val=swapnode->val;
*parent=tempparent;
if( (*parent)->val > swapnode->val ) {
(*parent)->left=NULL;
} else {
(*parent)->right=NULL;
}
if(swapnode->left != NULL)
(*parent)->right=swapnode->left; //new condition (for debug)
free(swapnode);
return;
}
}
No comments:
Post a Comment