Author:
b
[ Edit | View ]
|
Date Posted: 18:30:05 09/21/05 Wed
Author Host/IP: dsl-TN-024.246.247.61.touchtelindia.net/61.247.246.24
/*******Binary Search Tree Simulator v1.0******
This program simulates a binary search tree and
performs elementary search operations on it. It
includes the functionality to view the tree and
also to free the tree.There is another function
to optimise the binary search tree for maximum
search efficiency.The function to delete a node
from the tree allows deletion of all nodes but
the root node.This program has been released to
the public domain for academic purposes and for
making improvements.Suggested improvements are
an option to delete the root node of the tree
and to make the view tree function better which
I believe is pretty difficult.The globalpointer
root holds always points to the root.Please do
send me the improved versions of this program.
Author:Deepak
E-mail:deepak-p@eth.net
Computer Engg: Student,Kerala,India.
**********************************************/
# include /*Fordynamic memory allocation functions*/
# include
# include
struct node
{
int key;
struct node *left;
struct node *right;
};
struct node *root,*t1,*t2;
int count=0,arrcount=0,comp=0;
int *array;
void inittree(int i)
{
root=(struct node *)malloc(sizeof(struct node));
root->key=i;
root->left=NULL;
root->right=NULL;
count++;
}
void add2tree(struct node *t,int i)
{
struct node *p;
if((i>t->key)&&(t->right==NULL))
{
p=(struct node *)malloc(sizeof(struct node));
p->key=i;p->left=NULL;p->right=NULL;
t->right=p;
return;
}
if((ikey)&&(t->left==NULL))
{
p=(struct node *)malloc(sizeof(struct node));
p->key=i;p->left=NULL;p->right=NULL;
t->left=p;
return;
}
if(i>t->key)add2tree(t->right,i);
else if(ikey)add2tree(t->left,i);
}
void inorder(struct node *t)/*Inorder traversal of the tree***/
{
if(t==NULL)return;
inorder(t->left);
printf("\n%d",t->key);
inorder(t->right);
}
/*****Set arrcount (global)to 0 before calling this function****/
void print2array(struct node *t)
{
if(t==NULL)return;
print2array(t->left);
array[arrcount]=t->key;
arrcount++;
print2array(t->right);
}
/******Set arrcount(global)to 0 before calling this function*****/
void getno(struct node *t)/*To get no of elements*/
{
if(t==NULL)return;
getno(t->left);
arrcount++;
getno(t->right);
}
void freetree(struct node *t)
{
if(t==NULL)return;
if(t->left!=NULL)freetree(t->left);
if(t->right!=NULL)freetree(t->right);
t->right=NULL;t->left=NULL;t=NULL;t->key=NULL;
free(t);
}
struct node *makeoptree(int *arr,int a,int b)/*Tree optimiser*/
{
struct node *t1,*t2;
int n=b-a+1;
if(n==1)
{
t2=(struct node *)malloc(sizeof(struct node));
t2->key=arr[a];
t2->left=NULL;
t2->right=NULL;
return t2;
}
if(n==0)
{
return NULL;
}
t1=(struct node *)malloc(sizeof(struct node));
t1->key=arr[(int)(a+n/2)];
t1->left=makeoptree(arr,a,(int)(a+n/2-1));
t1->right=makeoptree(arr,(int)(a+n/2+1),b);
return t1;
}
int search(struct node *t,int i)
{
comp++;
if(i==t->key){return 1;}
if((ikey)&&(t->left==NULL)){return 0;}
if((i>t->key)&&(t->right==NULL)){return 0;}
if(ikey){return search(t->left,i);}
if(i>t->key){return search(t->right,i);}
return 0;
}
void callsearch()
{
int i,j;
printf("\nEnter an element to be searched:");
scanf("%d",&i);
comp=0;
j=search(root,i);
if(j==1)
{
printf("\nFound after %d comparisons\n\n",comp);
return;
}
else if(j==0)
{
printf("\nCould not find after %d comparisons\n\n",comp);
return;
}
}
void viewtree(struct node *t,int x,int y)
{
if(t==NULL)return;
gotoxy(x,y);
printf("%d",t->key);
viewtree(t->left,x-4,y+1);
viewtree(t->right,x+4,y+1);
}
struct node *getparent(struct node *t,int i)
{
int n=search(t,i);
if(n==0)
{
return NULL;
}
if((i>t->key)&&(i==t->right->key))
{return t;}
else if(i>t->key)
{return getparent(t->right,i);}
if((ikey)&&(i==t->left->key))
{return t;}
else if(ikey)
{return getparent(t->left,i);}
return NULL;
}
struct node * getnode(struct node *t,int i)
{
if(search(t,i)==0)return NULL;
if(t->key==i)return t;
else if(i>t->key)return getnode(t->right,i);
else if(ikey)return getnode(t->left,i);
return NULL;
}
struct node *getsuccessor(int i)
{
struct node *a;
int j,len;
if(search(root,i)==0)return NULL;
arrcount=0;getno(root);len=arrcount;
array=(int *)calloc(len,sizeof(int));
arrcount=0;print2array(root);
for(j=0;j<(len-1);j++)
{
if(i==array[j])
{
a=getnode(root,array[j+1]);
free(array);
}
}
if(i==array[len-1])
{
free(array);
return NULL;
}
return a;
}
int deleteitem(int i)
{
struct node *a,*b,*c,*d;
a=getnode(root,i);
b=getparent(root,i);
c=getsuccessor(i);
if(search(root,i)==0)
return -1;
if((a->left==NULL) && (a->right==NULL))
{
if(b->right==a)b->right=NULL;
else b->left=NULL;
a=NULL;
free(a);
return 0;
}
else if((a->left!=NULL)&&(a->right==NULL))
{
if(b->left==a)
b->left=a->left;
else
b->right=a->left;
a=NULL;
free(a);
return 0;
}
else if((a->right!=NULL)&&(a->left==NULL))
{
if(b->left==a)
b->left=a->right;
else
b->right=a->right;
a=NULL;
free(a);
return 0;
}
}
int intro()
{
int i;
clrscr();
printf("Binary Search Tree Simulator 1.0\n\n\n");
printf("\n1.Add Items to the tree");
printf("\n2.View the tree");
printf("\n3.Optimise tree");
printf("\n4.Search for an element");
printf("\n5.Free the tree");
printf("\n6.Input an element to get parent");
printf("\n7.Delete an item");
printf("\n8.Input an element to get successor");
printf("\n9.Exit\n");
printf("\nEnter your response:");
scanf("%d",&i);
fflush(stdin);
clrscr();
return i;
}
main()
{
int i,n;
abc: i=intro();
if(i==1)
{
printf("\nEnter the element to be added to the tree:");
scanf("%d",&n);fflush(stdin);
arrcount=0;getno(root);
if(arrcount==0){inittree(n);}
else {add2tree(root,n);}
goto abc;
}
else if(i==2)
{
clrscr();
arrcount=0;getno(root);
if(arrcount==0){printf("\nEmpty tree");}
else{viewtree(root,38,1);}
getch();
goto abc;
}
else if(i==3)
{
arrcount=0;getno(root);
array=(int *)calloc(arrcount,sizeof(int));
arrcount=0;
print2array(root);
freetree(root);
root=makeoptree(array,0,arrcount-1);
printf("\nTree optimisation finished");getch();
free(array);
goto abc;
}
else if(i==4)
{
callsearch();
getch();
goto abc;
}
else if(i==5)
{
freetree(root);root=NULL;
printf("\nBinary tree has been freed");
getch();
goto abc;
}
else if(i==6)
{
printf("\nEnter an element to find the parent:");
scanf("%d",&n);fflush(stdin);
t1=getparent(root,n);
if(t1!=NULL)
printf("\nParent is %d",t1->key);
else
printf("\nElement not present or is the root");
getch();
goto abc;
}
else if(i==7)
{
printf("\nEnter an element to delete:");
scanf("%d",&n);
if(search(root,n)==0)
printf("\nElement not present");
else
{
deleteitem(n);
printf("\nItem deleted");
}
getch();
goto abc;
}
else if(i==8)
{
printf("\nEnter an element to find successor:");
scanf("%d",&n);fflush(stdin);
t1=getsuccessor(n);
if(t1==NULL)
printf("\nElement not present or has no successor");
else
printf("\nSuccessor is %d",t1->key);
getch();
goto abc;
}
else if(i==9)
{
printf("\nThank you");
getch();
exit(0);
}
return;
}
[ Post a Reply to This Message ]
|
Feedback: 