VB icon

A Binary Search Tree (BST)

Email
Submitted on: 1/3/2015 9:29:00 PM
By: Arati Rajbhandari Joshi (from psc cd)  
Level: Beginner
User Rating: By 9 Users
Compatibility: C, C++ (general), Borland C++
Views: 2305
 
     This BST code will be useful to everyone who wants to know about the basic operations of a BST like Insertion, Deletion, Make Empty, Find Minimum, Find Maximun, Search, Traverse Ascending, and Traverse Descending. Do leave some comments on this code!!
 
code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
				
//**************************************
// Name: A Binary Search Tree (BST)
// Description:This BST code will be useful to everyone who wants to know about the basic operations of a BST like Insertion, Deletion, Make Empty, Find Minimum, Find Maximun, Search, Traverse Ascending, and Traverse Descending. Do leave some comments on this code!!
// By: Arati Rajbhandari Joshi (from psc cd)
//**************************************

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<process.h>
struct node{
	int info;
struct node *right;
struct node *left;
};
typedef struct node *BST;
typedef struct node node;
BST makeempty(BST t)
{
 	if (t!=NULL) {
	makeempty(t->left);
 makeempty(t->right);
 free(t);
}
return NULL;
}
BST find(BST t, int x)
{
 	if (t==NULL) return NULL;
if (x<t->info) return find(t->left,x);
else
if (x>t->info) return find(t->right,x);
else
return t;
}
BST findmin(BST t)
{
	if(t==NULL) return NULL;
else
	if(t->left==NULL) return t;
else return findmin(t->left);
}
BST findmax(BST t)
{
	if(t==NULL) return NULL;
else
	if(t->right==NULL) return t;
else return findmax(t->right);
}
BST insertnode(BST t, int x)
{
if(t==NULL) {
	t=(node*)malloc(sizeof(node));
 if(t==NULL) printf("\n Out of Space !!");
 else {
 	t->info = x;
 t->left = t->right = NULL;
 }
}
else
if (x<t->info) {
	t->left=insertnode(t->left,x);
}
else
if (x>t->info) {
	t->right=insertnode(t->right,x);
}
return t;
}
BST deletenode(BST t, int x)
{
	BST tmpcell;
	if(t == NULL) {
	printf("\n Cannot Delete!! No Such Value Found");
}
else
if(x < t->info) t->left = deletenode(t->left,x);
else
if(x > t->info) t->right = deletenode(t->right,x);
else
 	if(t->right && t->left){
	tmpcell = findmin(t->right);
 t->info = tmpcell->info;
 t->right = deletenode(t->right,tmpcell->info);
}
else {
	tmpcell = t;
 if(t->left == NULL) t = t->right;
 else if(t->right == NULL) t = t->left;
 free(tmpcell);
 printf("\n Value Successfully Deleted.");
}
return t;
}
void printtree_asc(BST t)
{
 	if (t!=NULL) {
	printtree_asc(t->left);
 printf("\n %d",t->info);
 printtree_asc(t->right);
}
}
void printtree_desc(BST t)
{
 	if (t!=NULL) {
	printtree_desc(t->right);
 printf("\n %d",t->info);
 printtree_desc(t->left);
}
}
main()
{
	BST tree, pos;
char ans;
int val;
tree=NULL;
while(1){
	printf(" Binary Search Tree (BST)");
	printf("\n\n [1].\tInsert\n");
 printf(" [2].\tDelete\n");
 printf(" [3].\tMake Empty\n");
 printf(" [4].\tFind Minimum\n");
 printf(" [5].\tFind Maximun\n");
 printf(" [6].\tSearch\n");
 printf(" [7].\tPrint Ascending\n");
 printf(" [8].\tPrint Descending\n");
 printf(" [9].\tExit\n\n");
 printf(" Enter Choice: ");
 		ans = getche();
 switch(ans)
 {
 	case '1':
 {
 	printf("\n Enter Value: ");
 	scanf("%d",&val);
 	tree=insertnode(tree,val);
 }
 break;
 case '2':
 {
 	if(tree!=NULL) {
 	printf("\n Enter Value to be Deleted: ");
 	scanf("%d",&val);
 	tree=deletenode(tree,val);
 }
 else printf("\n Cannot Delete!! Empty BST!!");
 getch();
 }
 break;
 case '3':
 {
 	tree = makeempty(tree);
 	printf("\n BST is now Empty!!");
 	getch();
 }
 break;
 case '4':
 {
 	pos=findmin(tree);
 	if (pos!=NULL)
 		printf("\n Minimum Value: %d",pos->info);
 	else
 		printf("\n Empty BST!! No Minimum Value.");
 	getch();
 }
 break;
 case '5':
 {
 	pos=findmax(tree);
 	if (pos!=NULL)
 		printf("\n Maximum Value: %d",pos->info);
 	else
 		printf("\n Empty BST!! No Maximum Value.");
getch();
 }
 break;
 case '6':
 {
 if (tree!=NULL) {
 	printf("\n Enter Value to be Searched: ");
 	scanf("%d",&val);
 	pos=find(tree, val);
 	if (pos!=NULL)
 		printf("\n %d is found in the BST",pos->info);
else
 		printf("\n %d not found in the BST",val);
 }
 else {
 	printf("\n The BST is Empty!!");
 }
 getch();
 }
 break;
 case '7':
 {
 	if(tree!=NULL) {
 	clrscr();
 	printf("\n BST IN ASCENDING ORDER\n\n");
 	printtree_asc(tree);
 }
 else printf("\n Empty BST!!");;
 getch();
 }
 break;
 case '8':
 {
 	if(tree!=NULL) {
 	clrscr();
 	printf("\n BST IN DESCENDING ORDER\n\n");
 	printtree_desc(tree);
 }
 else printf("\n Empty BST!!");
 getch();
 }
 break;
 case '9':
 exit(0);
 default :
 {
 	printf("\n\n Choose from 1 to 9 only!!");
 	getch();
 }
 break;
 }
 clrscr();
}
}


Other 2 submission(s) by this author

 


Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this code (in the Beginner category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)
 

Other User Comments


 There are no comments on this submission.
 

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)
 

To post feedback, first please login.