C++ Program to implement Binary Search Tree Operations

By | January 9, 2017

Binary Search Tree Operations


Write a C++ Program to implement Binary Search Tree Operations. Here’s simple C++ Program to implement Binary Search Tree Operations in C++ Programming Language.


What is Tree ?


In linear data structure, data is organized in sequential order and in non-linear data structure, data is organized in random order. Tree is a very popular data structure used in wide range of applications.

A tree data structure can be defined as follows…

  • Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

A tree data structure can also be defined as follows…

  • Tree data structure is a collection of data (Node) which is organized in hierarchical structure and this is a recursive definition.

Every individual element is called as Node. Node in a tree data structure, stores the actual data of that particular element and link to next element in hierarchical structure.


Below is the source code for C++ Program to implement Binary Search Tree Operations which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/*  C++ Program to implement Binary Search Tree Operations  */

#include<iostream>
#include<stdlib.h>

using namespace std;
 
void insert(int,int );
void delte(int);
void display(int);
int search(int);
int search1(int,int);
int tree[40],t=1,s,x,i;
 
int main()
{
	int ch,y;
	for(i=1;i<40;i++)
	tree[i]=-1;
	while(1)
	{
cout <<"1.INSERT\n2.DELETE\n3.DISPLAY\n4.SEARCH\n5.EXIT\nEnter your choice:";
		cin >> ch;
		switch(ch)
		{
		case 1:
			cout <<"enter the element to insert";
			cin >> ch;
			insert(1,ch);
			break;
		case 2:
			cout <<"enter the element to delete";
			cin >>x;
			y=search(1);
			if(y!=-1) delte(y);
			else cout<<"no such element in tree";
			break;
		case 3:
			display(1);
			cout<<"\n";
			for(int i=0;i<=32;i++)
			cout <<i;
			cout <<"\n";
			break;
case 4:
			cout <<"enter the element to search:";
			cin >> x;
			y=search(1);
			if(y == -1) cout <<"no such element in tree";
			else cout <<x << "is in" <<y <<"position";
			break;
		case 5:
			exit(0);
		}
	}
    return 0;
}
 
void insert(int s,int ch )
{
	int x;
	if(t==1)
	{
		tree[t++]=ch;
		return;
	}
	x=search1(s,ch);
	if(tree[x]>ch)
		tree[2*x]=ch;
	else
		tree[2*x+1]=ch;
	t++;
}
void delte(int x)
{
	if( tree[2*x]==-1 && tree[2*x+1]==-1)
		tree[x]=-1;
	else if(tree[2*x]==-1)
	      {	tree[x]=tree[2*x+1];
		tree[2*x+1]=-1;
	      }
	else if(tree[2*x+1]==-1)
	      {	tree[x]=tree[2*x];
		tree[2*x]=-1;
	      }
	else
	{
	  tree[x]=tree[2*x];
	  delte(2*x);
	}
	t--;
}
 
int search(int s)
{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return tree[s];
if(tree[s]>x)
search(2*s);
else if(tree[s]<x)
search(2*s+1);
else
return s;
}
 
void display(int s)
{
if(t==1)
{cout <<"no element in tree:";
return;}
for(int i=1;i<40;i++)
if(tree[i]==-1)
cout <<" ";
else cout <<tree[i];
return ;
}
 
int search1(int s,int ch)
{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return s/2;
if(tree[s] > ch)
search1(2*s,ch);
else search1(2*s+1,ch);
}

OUTPUT : :


1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:1
enter the element to insert4
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:1
enter the element to insert2
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:1
enter the element to insert9
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:1
enter the element to insert7
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:1
enter the element to insert5
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:3
429  7     5                           

1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:4
enter the element to search:9
9 is in 3position
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:2
enter the element to delete1
no such element in tree
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:2
enter the element to delete4
1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:3
2 9  7     5                           

1.INSERT
2.DELETE
3.DISPLAY
4.SEARCH
5.EXIT
Enter your choice:5
 
Exit code: 0

Above is the source code and output for C++ Program to implement Binary Search Tree Operations which is successfully compiled and run on Windows System to produce desired output.

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach upto you in the short interval.


Thanks for reading the post….

Leave a Reply