/* bst.cpp*/
#include<iostream.h>
#include<conio.h>
#include<process.h>
struct rec
{
long num;
struct rec *left;
struct rec *right;
};
struct rec *tree;
class ctree{
public: struct rec *delnum(long,struct rec *);
struct rec *insert(struct rec *,long);
struct rec *deletenode(long,struct rec *);
void search(struct rec *,long);
void preorder(struct rec *);
void inorder(struct rec *);
void postorder(struct rec *);
int select();
ctree()
{
tree=NULL;
}
};
void main()
{
int choice;
long digit;
int element;
ctree ct;
clrscr();
do
{
choice=ct.select();
switch(choice)
{
case 1: cout<<"Enter integer: To quit enter 0"<<endl;
cin>>digit;
while(digit!=0)
{
tree=ct.insert(tree,digit);
cin>>digit;
}continue;
case 2: cout<<"Enter the number to be search";
cin>>digit;
ct.search(tree,digit);
continue;
case 3: cout<<endl<<"preorder traversing TREE";
ct.preorder(tree);continue;
case 4: cout<<endl<<"inorder traversing TREE";
ct.inorder(tree);continue;
case 5: cout<<endl<<"postorder traversing TREE";
ct.postorder(tree);continue;
case 6: cout<<"Enter element which do you want delete from the BST";
cin>>digit;
ct.deletenode(digit,tree);continue;
case 7: cout<<"END";
exit(0);
}
}while(choice!=7);
}
int ctree::select()
{
int selection;
do
{
cout<<endl<<"Enter 1: Insert a node in the BST";
cout<<endl<<"Enter 2: Search a node in BST";
cout<<endl<<"Enter 3: Display(preorder)the BST";
cout<<endl<<"Enter 4: Display(inorder)the BST";
cout<<endl<<"Enter 5: Display(postorder) the BST";
cout<<endl<<"Enter 6: Delete the element";
cout<<endl<<"Enter 7: END";
cout<<endl<<"Enter your choice ";
cin>>selection;
if((selection<1)||(selection>7))
{
cout<<"wrong choice:Try again";
getch(); }
}while((selection<1)||(selection>7));
return (selection);
}
struct rec * ctree::insert(struct rec *tree,long digit)
{
if(tree==NULL)
{
tree=new(struct rec);
tree->left=tree->right=NULL;
tree->num=digit;
}
else
if(digit<tree->num)
tree->left=insert(tree->left,digit);
else
if(digit>tree->num)
tree->right=insert(tree->right,digit);
else if(digit==tree->num)
{
cout<<"Duplicate node:program exited";
exit(0);
}
return(tree);
}
//copy from here
struct rec * ctree::delnum(long digit,struct rec *r)
{
struct rec *q;
if(r->right!=NULL)delnum(digit,r->right);
else
q->num=r->num;
q=r;
r=r->left;
}
struct rec * ctree::deletenode(long digit,struct rec *tree)
{
struct rec *r,*q;
if(tree==NULL)
{
cout<<endl<<"Tree is empty.";
exit(0);
}
if(digit<tree->num)
deletenode(digit,tree->left);
else
if(digit>tree->num)deletenode(digit,tree->right);
q=tree;
if((q->right==NULL)&&(q->left==NULL))
q=NULL;
else
if(q->right==NULL)tree=q->left;else
if(q->left==NULL)tree=tree=q->right;else
delnum(digit,q->left);
delete(q);
}
void ctree::search(struct rec *tree,long digit)
{
if(tree==NULL)
cout<<"The number does not exits"<<endl;
else
if(digit==tree->num)
cout<<endl<<"Number is "<<digit;
else
if(digit<tree->num)
search(tree->left,digit);
else
search(tree->right,digit);
}
void ctree::preorder(struct rec *tree)
{
if(tree!=NULL)
{
cout<<endl<<tree->num;
preorder(tree->left);
preorder(tree->right);
}
}
void ctree::inorder(struct rec *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
cout<<endl<<tree->num;
inorder(tree->right);
}
}
void ctree::postorder(struct rec *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
cout<<endl<<tree->num;
}
}
/*The output of the above program is:-
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 1
Enter integer: To quit enter 0
82
77
90
346
0
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 2
Number is 35
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 3
preorder traversing TREE
82
77
35
90
346
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 4
inorder traversing TREEE
35
77
82
90
346
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 5
postorder traversing TREE
35
77
346
90
82
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 6
Enter element which do you want delete from the BST82
Enter 1: Insert a node in the BST
Enter 2: Search a node in BST
Enter 3: Display(preorder)the BST
Enter 4: Display(inorder)the BST
Enter 5: Display(postorder) the BST
Enter 6: Delete the element
Enter 7: END
Enter your choice 7*/
------------------------------------------------------------------------------------------------------------
//binary search traversal by using recursive method
#include<iostream.h>
#include<conio.h>
#include<stdio.h>//null is macro, defined in stdio.h
template <class T>
class node
{
node<T> * lchild;//lchild contain addrss of left child
T data;//data field contains value
node<T> * rchild;
friend class tree<T>;//we can access lchild, data,rchild from tree class
//we can access lchild, data,rchild from these functions
friend void rpreorder(node<T> *p);
friend void rpostorder(node<T> *p);
friend void rinorder(node<T> *p);
};
//t7(3).wav
template<class T>
class tree
{
private:
node<T> *root;//root is a pointer to root node
public:
tree();
~tree();
int isempty();
void create();
void traverse();
void rpreorder();
void rinorder();
void rpostorder();
node<t> * search(T x);
void insert(node<T> *k);
};
template<class T>
tree<T>::tree()
{
root=NULL;
}
template <class T>
int tree<T>::isempty()
{
return(root==NULL);
}
//t8(3).wav
template <class T>
void tree<T>::rpreorder(node<T> *p)
{
if( p != NULL)
{
cout<<p->data);
rpreorder(p->lchild);
rpreorder(p->rchild);
}
}
//rpreorder(root);
template <class T>
void tree<T>::rinorder(node<T> *p)
{
if(p != NULL)
{
rinorder(p->left);
cout<<p->data;
rinorder(p->right);
}
}
template <class T>
void tree<T>::rpostorder(node<T> *p)
{
if( p != NULL)
{
rpostorder(p->left);
rpostorder(p->right);
cout<<p->data);
}
}
template <class T>
node<T>* tree<T>::search(T x)//X IS VALUE 2 BE SEARCHD IN DA BINARY TREE
{
node<t> *p;
p=root; //P POINTS TO ROOT NODE
while(p!=NULL)//SEARCH FOR X IN THE TREE UNTIL BECOMES NULL
{
if(x==p->data) //IF X IS FOUND IN NODE P, RETURN ADRESS OF THT NODE
return(p);
else
if(x<p->data) //SEARCH FOR X IN LEFT SUB TREE
p=p->lchild; // MOVE POINTER P TO LEFT CHILD
else //SEARCH FOR X IN THE RIGHT SUB TREE
p=p->rchild; //MOVE POINTER TO RIGHT CHILD
}
return(NULL);//X IS NOT FOUND IN THE TREE
}
template<class T>
void tree<T>::insert(node,T> *k)//k is poiner to node to be inserted
{
node<T> *p;
if(isempty())//IF TREE IS EMPTY, NODE K IS ROOT NODE
{
root=k;//ROOT PTR TO THE NEW NODE
return;//SKIP REST OF THE FUNCTION
}
p=root;//P POINTS TO ROOT NODE
while(1)//ALWAYS TRUE
{
if(k->data<p->data)//INSERT NODE K IN THE LEFT SUB TREE
{
if(p->lchild!=NULL)//IF LEFT CHILD EXISTS, MOVE PTR P TO LEFTCHILD
p=p->lchild;
else//IF THERE IS NO LEFT CHILD, NODE K BECOMES LEFT CHILD OF P
{
p->lchild=k;//ATTACH NODE K AS LEFT CHILD OF P
return;//COME OUT OF FUNCTION TO AVOID INFINITE LOOP
}
}
else
if(k-data>p->data)//INSERT NODE K IN THE RIGHT SUB TREE
{
if(p->rchild!=NULL)//IF RIGHT CHILD EXISTS,MOVE PTR P TO RIGHTCHILD
p=p->rchild;
else//IF THERE IS NO RIGHT CHILD K BECOMES RIGHT CHILD OF P
{
p->rchild=k;//ATTACH NODE K AS RIGHT CHILD OF P
return;//COME OUT OF FUNCTION SOON AFTER INSERTION
}//VALUE ALREADY EXISTS IN THE TREE
}
else
{
cout<<k->data<<"already exists. Insertion is not possible\n";
return;
}
}
}
}
//t8(6).wav
template <class T>
void tree<T>::create()
{
T x;
node<T> *k;
root=NULL;//initially tree is empty
cout<<"ENTER VALUE TERMINATES BY -1 OR !\n";
cin>>x;//read the 1st no's which is root node
while(x!=-1&&x!='!')//execute loop until user types -1 or !
{
k=new node<T>; //create a node, k is pointer to it
k->data=x;//store x in the new node data field
k->lchild=k->rchild=NULL;//initially node k is leaf node
insert(k);//isnert node k in binary tree in appropriate place
cin>>x;//read next number
}
}
void menu1()
{
cout<<"1. rpreorder\n";
cout<<"2. rinorder\n";
cout<<"3. rpostorder\n";
cout<<"4. exit\n"; //levelorder() is not wrote
}
//t8(4)
template <class T>
void tree<T>::traverse()
{
int ch;
clrscr();
menu1();
cout<<"enter ur choice\n";
cin>>ch;
while(ch<5)
{
switch(ch)
{
case 1: {
rpreorder();//calling recursive() from intermediate fun
break;
}
case 2: {
rinorder();
break;
}
case 3: {
rpostorder();
break;
}
}
menu1();
cout<<"enter ur choice\n";
cin>>ch;
}
}
//a.traverse();
//t10.wav(2)
void main()
{
node<int> *p;
int ch, x;
tree<int>a;
clrscr();
a.create();
clrscr();
cout<<"enter ur choice 1. traverse \n 2. search";
cin>>ch;
while(ch<3)
{
switch(ch)
{
case 1: {
//traverwse binary tree in tree, pose, inorder
//it is a intermediate function
a.traverse();
break;
case 2: {
cout<<"enter value to be searched \n";
cin>>x;
p=a.search(x);//it returns adres of dat node whre x is found
if(p==NULL)
cout<<"it is not found\n";
else
cout<,"it is found at address="<<p<<"\n";
break;
}
}//switch
cout<<"enter ur choice 1. traverse \n 2. search";
cin>>ch;
}//while
getch();
}//destructor is called before object a is lost
