Program for binary search tree in C++.

#include<iostream.h>            //INCLUDING LIBRARIES
#include<fstream.h>


struct node                        //DECLARING NODE DATA STRUCTURE
{
int data;
node *left, *right;
}*root, *cur ,*temp;

void pretrav (node *);            //FUNCTION PROTOTYPE FOR PRETRAVERSAL OF BINARY TREE
void intrav (node *);            //FUNCTION PROTOTYPE FOR INORDER TRAVERSAL OF BINARY TREE
void posttrav (node *);            //FUNCTION PROTOTYPE FOR POSTTRAVERSAL OF BINARY TREE

void main()                        //START OF MAIN
{
cout<<"\t\t\t  BINARY SEARCH TREE\n\n";
cout<<"\n\nDuplicates in the tree : ";
char ch,sign;
int num,count=0,countdup=0;;
ifstream fin;
fin.open("integer.txt");    //OPENING TEXT FILE CONTAINING INTEGERS AND STORING THE RETURNED PTR IN FIN

while(fin)                    //EXECUTE THE LOOP TILL THE END OF FILE
{

fin.get(ch);            //READ A CHARACTER FROM THE FILE

if (ch==' ')            //IF SPACE CONTINUE
continue;

if (ch=='+'||ch=='-')    //STORING THE SIGN OF NUMBER
sign=ch;

if (ch>='0'&&ch<='9')    //IF DIGIT ENCOUNTERED
{
fin.seekg(-1,ios::cur);
fin>>num;                //READING NUMBER IF DIGIT ENCOUNTERED
count++;                //INCREMENTING THE COUNTER
if (sign=='-')            //MAKING THE NUMBER NEGATIVE AND STORING IN NUM
num=0-num;
sign='+';                //MAKING SIGH POSITIVE ...DEFAULT
temp=new node;            //CREATING NEW NODE
temp->data=num;            //STORING THE NUM IN NEW NODE
temp->left=temp->right=NULL;        //MAKING LEFT & RIGHT PTRS OF TEMP NULL


cur=root;                //POINTING CUR PTR TO THE ROOT
if (count==1)            //IF ITS FIRST NODE MAKE IT ROOT
root=temp;
else
{
while(1)
{
if (cur->data<temp->data)
{
if (cur->right!=NULL)
cur=cur->right;        //MOVING CUR POINTER
else
{
cur->right=temp;
break;                //EXIT OUT OF WHILE LOOP
}
}

if (cur->data>temp->data)
{
if (cur->left!=NULL)
cur=cur->left;        //MOVING CUR POINTER
else
{
cur->left=temp;
break;                //EXIT OUT OF WHILE LOOP
}
}


if (cur->data==temp->data)
{
cout<<num<<"  ";        //PRINTING DUPLICATES
countdup++;
break;
}

}
}
}
}
if (countdup==0)
cout<<" None";

cout<<"\n\nPreorder Traversal of the Tree : ";
pretrav(root);                                    //CALLING FUNCTION FOR PREORDER TRAVERSAL OF TREE PASSING ROOT
cout<<endl<<endl;
cout<<"Inorder Traversal  of the Tree : ";
intrav (root);                                    //CALLING FUNCTION FOR INORDER TRAVERSAL OF TREE PASSING ROOT
cout<<endl<<endl;
cout<<"Postorder Traversal of the Tree: ";
posttrav(root);                                    //CALLING FUNCTION FOR POSTORDER TRAVERSAL OF TREE PASSING ROOT
cout<<endl<<endl;

}

void pretrav (node * point)                //DECLARING FUNCTION FOR PRETRAVERSAL OF THE TREE
{
cout<<" "<<point->data<<" ";
if (point->left!=NULL)
pretrav (point->left);

if (point->right!=NULL)
pretrav (point->right);
}


void intrav (node * point)                //DECLARING FUNCTION FOR INORDER TRAVERSAL OF THE TREE
{
if (point->left!=NULL)
intrav (point->left);
cout<<" " <<point->data<<" ";
if (point->right!=NULL)
intrav (point->right);



}

void posttrav (node *point)                //DECLARING FUNCTION FOR POSTORDER TRAVERSAL OF THE TREE
{
if (point->left!=NULL)
intrav (point->left);
if (point->right!=NULL)
intrav (point->right);
cout<<" " <<point->data<<" ";
}
       //END OF PROGRAM//
Advertisements

One thought on “Program for binary search tree in C++.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s