Program to show Implementation of Binary Tree using Linked list

#include"stdio.h"
#include"conio.h"
#include"alloc.h"
#include"stdlib.h"

struct btree
{
int n;
struct btree *left;
struct btree *right;
}typedef btree,node;
btree *root,*ptr,*prev,*bfor,*x,*y;
int num;
char ch;

void main()
{
int c;
void create(node *);
void print(node *);
void search(node *);
void insert(node *);
void modify(node *);
void delet(node *);

while(c!=7)
{
clrscr();
printf("1. CREATE");
printf("2. PRINT");
printf("3. SEARCH");
printf("4. INSERT");
printf("5. MODIFY");
printf("6. DELETE");
printf("7. EXIT");
printf("Enter your choice : ");
scanf("%d",&c);
switch(c)
{
case 1 :
{
root=(node *)malloc(sizeof(node));
printf("Enter number : ");
scanf("%d",&root->n);
ptr=root;
root->left=root->right=NULL;
printf("Enter more(y/n)? ");
ch=getch();
create(root);
break;
}

case 2 :
{
print(root);
getch();
break;
}
case 3 :
{
printf("");
search(root);
getch();
break;
}
case 4 :
{
printf("");
insert(root);
getch();
break;
}
case 5 :
{
printf("");
modify(root);
getch();
break;
}
case 6 :
{
printf("");
delet(root);
getch();
break;
}
case 7 :
exit(0);

default:
{
printf("Invalid choice");
getch();
break;
}
}
}
getch();
}

void create(node *ptr)
{
while(ch == 'y')
{
printf("");
ptr=prev=root;
printf("Enter number : ");
scanf("%d",&num);
do
{
if(num <>n)
{
prev=ptr;
ptr=ptr->left;
}
else if(num > ptr->n)
{
prev=ptr;
ptr=ptr->right;
}
else
{
prev=NULL;
break;
}
}while(ptr);

if(prev)
{
ptr=(node *)malloc(sizeof(node));
ptr->n=num;
ptr->left=ptr->right=NULL;
if(ptr->n <>n)
{
prev->left=ptr;
if(prev == root)
root=prev;
}
if(ptr->n > prev->n)
{
prev->right=ptr;
ptr->left=ptr->right=NULL;
if(prev == root)
root=prev;
}
}
else
printf("'%d' is already present..",num);

printf("Enter more(y/n)? ");
ch=getch();
}
}

void print(node *ptr)
{
void inprint(node *);
void preprint(node *);
void postprint(node *);

if(!ptr)
{
printf("Tree is empty...");
return;
}
printf("Root is '%d'",root->n);
printf("INORDER : ");
inprint(root);
printf("PREORDER : ");
preprint(root);
printf("POSTORDER : ");
postprint(root);
}


void inprint(node *ptr)
{
if(!ptr)
return;

inprint(ptr->left);
printf("%2d ",ptr->n);
inprint(ptr->right);
return;
}

void preprint(node *ptr)
{
if(!ptr)
return;

printf("%2d ",ptr->n);
preprint(ptr->left);
preprint(ptr->right);
return;
}
void postprint(node *ptr)
{
if(!ptr)
return;

postprint(ptr->left);
postprint(ptr->right);
printf("%2d ",ptr->n);
return;
}

void search(node *ptr)
{
if(!ptr)
{
if(ptr == root)
{
printf("Tree is empty... You can't search anything...");
return;
}
}
printf("Enter the number to search : ");
scanf("%d",&num);

while(ptr)
{
if(ptr->n == num)
{
printf("Success... You found the number...");
return;
}
else
if(ptr->n < ptr="ptr-">right);
else
ptr=ptr->left;
}
printf("Tree don't contain '%d'...",num);
}

void insert(node *ptr)
{
if(!ptr)
{
printf("Tree is empty...First create & then insert... ");
return;
}
printf("");
ptr=prev=root;
printf("Enter number to be inserted : ");
scanf("%d",&num);

do
{
if(num <>n)
{
prev=ptr;
ptr=ptr->left;
}
else if(num > ptr->n)
{
prev=ptr;
ptr=ptr->right;
}
else
{
prev=NULL;
break;
}
}
while(ptr);

if(prev)
{
ptr=(node *)malloc(sizeof(node));
ptr->n=num;
ptr->left=ptr->right=NULL;

if(ptr->n <>n)
{
prev->left=ptr;
if(prev == root)
root=prev;
}
if(ptr->n > prev->n)
{
prev->right=ptr;
ptr->left=ptr->right=NULL;
if(prev == root)
root=prev;
}
printf("'%d' is inserted...",num);
}
else
printf("'%d' is already present...",num);
return;
}

void modify(node *ptr)
{
int mod;
if(!ptr)
{
if(ptr == root)
{
printf("Tree is empty... You can't modify anything...");
return;
}
}
printf("Modification of particular number can't create a binary
tree...");
getch();
printf("Enter the number to get modified : ");
scanf("%d",&num);
prev=ptr;
while(ptr)
{
if(ptr->n == num)
{
x=ptr;
mod=x->n;
printf("Then enter new number : ");
scanf("%d",&num);
bfor=ptr=root;
while(ptr)
{
if(ptr->n == num)
{
printf("'%d' already present...Modification denied...,",num);
return;
}
else if(ptr->n < bfor="ptr;" ptr="ptr-">right;
}
else
{
bfor=ptr;
ptr=ptr->left;
}
}
if(x==root)
{
y=x->right;
root=y;
while(y->left)
y=y->left;
y->left=x->left;
free(x);
}
else if(!(x->left) && !(x->right))
{
if(prev->left == x)
{
prev->left=NULL;
free(x);
}
else if(prev->right == x)
{
prev->right=NULL;
free(x);
}
}
else if(!(x->left))
{
if(prev->left == x)
{
prev->left=x->right;
free(x);
}
else if(prev->right == x)
{
prev->right=x->right;
free(x);
}
}
else if(!(x->right))
{
if(prev->left == x)
{
prev->left=x->left;
free(x);
}
else if(prev->right == x)
{
prev->right=x->left;
free(x);
}
}
else
{
y=x->right;
while(y->left)
y=y->left;
y->left=x->left;
if(prev->left == x)
prev->left=y;
else if(prev->right == x)
prev->right=y;
free(x);
}
ptr=(node *)malloc(sizeof(node));
ptr->n=num;
ptr->left=ptr->right=NULL;
if(ptr->n <>n)
{
bfor->left=ptr;
if(bfor == root)
root=bfor;
}
if(ptr->n > bfor->n)
{
bfor->right=ptr;
ptr->left=ptr->right=NULL;
if(bfor == root)
root=bfor;
}
printf("'%d' is modified by '%d'",mod,ptr->n);
return;
}
else
if(ptr->n < prev="ptr;" ptr="ptr-">right;
}
else
{
prev=ptr;
ptr=ptr->left;
}
}
printf("Tree don't contain '%d'...",num);
}

void delet(node *ptr)
{
if(!ptr)
{
if(ptr == root)
{
printf("Tree is empty... You can't delete anything...");
return;
}
}
printf("Enter the number to get deleted : ");
scanf("%d",&num);
prev=ptr;

while(ptr)
{
if(ptr->n == num)
{
if(ptr==root)
{
x=ptr->right;
root=x;
while(x->left)
x=x->left;
x->left=ptr->left;
free(ptr);
printf("'%d' is deleted...",num);
return;
}
else if(!(ptr->left) && !(ptr->right))
{
if(prev->left == ptr)
prev->left=NULL;
else
prev->right=NULL;
free(ptr);
printf("'%d' is deleted...",num);
return;
}
else if(!(ptr->left))
{
if(prev->left == ptr)
{
prev->left=ptr->right;
free(ptr);
}
else if(prev->right == ptr)
{
prev->right=ptr->right;
free(ptr);
}
printf("'%d' is deleted...",num);
return;
}
else if(!(ptr->right))
{
if(prev->left == ptr)
{
prev->left=ptr->left;
free(ptr);
}
else if(prev->right == ptr)
{
prev->right=ptr->left;
free(ptr);
}
printf("'%d' is deleted...",num);
return;
}
else
{
x=ptr->right;
while(x->left)
x=x->left;
x->left=ptr->left;
if(prev->left == ptr)
prev->left=ptr->right;
else if(prev->right == ptr)
prev->right=ptr->right;
free(ptr);
printf("'%d' is deleted...",num);
return;
}
}
else if(ptr->n < prev="ptr;" ptr="ptr-">right;
}
else
{
prev=ptr;
ptr=ptr->left;
}
}
printf("Tree don't contain '%d'...",num);
}

Related Links :