Binary Tree

123 Eng

Engineering the engineers™

Home
Source Codes
Engineering Colleges
Training Reports
Seminar Reports
Placement Papers
Forums
   Computer Science / IT
   Electronics
   Electrical
   Mechanical
   Chemical
   Civil
   CAT / MBA
   GMAT / Foreign MBA
Latest Jobs

Engineering Jobs / Technical Jobs
Management Jobs

Sitemap
Terms of use

Displaying Source Code(s)

--------------------------------------------------------------------------------

Binary Tree

--------------------------------------------------------------------------------

Description : Implementation of Binary Tree using Linked list

Code :
#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 < ptr->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 < prev->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 < num)
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 < ptr->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 < prev->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 < num)
{
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 < bfor->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 < num)
{
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 < num)
{
prev=ptr;
ptr=ptr->right;
}
else
{
prev=ptr;
ptr=ptr->left;
}
}
printf("Tree don't contain '%d'...",num);
}