<br />#include<iostream>
#include <conio.h>
using namespace std;
struct tree
{
tree *l, *r;
int data;
}*root = NULL, *p = NULL, *np = NULL, *q,*t1,*t2;
void search1(struct tree *t,int data);
void display(tree *ptr, int level);
int smallest(struct tree *t);
int largest(struct tree *t);
void delete1(struct tree *t);
void create()
{
int value,n,c=0;
cout<<"how many number you want to insert:"<<endl;
cin>>n;
while (c < n)
{
if (root == NULL)
{
root = new tree;
cout<<"enter value of root node:"<<endl;
cin>>root->data;
root->r=NULL;
root->l=NULL;
}
else
{
p = root;
cout<<"enter value of node:"<<endl;
cin>>value;
while(true)
{
if (value < p->data)
{
if (p->l == NULL)
{
p->l = new tree;
p = p->l;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in left"<<endl;
break;
}
else if (p->l != NULL)
{
p = p->l;
}
}
else if (value > p->data)
{
if (p->r == NULL)
{
p->r = new tree;
p = p->r;
p->data = value;
p->l = NULL;
p->r = NULL;
cout<<"value entered in right"<<endl;
break;
}
else if (p->r != NULL)
{
p = p->r;
}
}
}
}
c++;
}
}
void inorder(tree *p)
{
if (p != NULL)
{
inorder(p->l);
cout<<p->data<<"->";
inorder(p->r);
}
}
void preorder(tree *p)
{
if (p != NULL)
{
cout<<p->data<<"->";
preorder(p->l);
preorder(p->r);
}
}
void postorder(tree *p)
{
if (p != NULL)
{
postorder(p->l);
postorder(p->r);
cout<<p->data<<"->";
}
}
int maxDepth(struct tree* node)
{
if (node==NULL)
return 0;
else
{
int lDepth = maxDepth(node->l);
int rDepth = maxDepth(node->r);
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
void Delete()
{
int item;
if(root==NULL)
{
cout<<"No elements in a tree to deleten";
return;
}
cout<<"Enter the data to be deleted :n";
cin>>item;
t1=root;
t2=root;
search1(root,item);
}
void search1(struct tree *t,int item)
{
if(item>t->data)
{
t1=t;
search1(t->r,item);
}
else if(item < t->data)
{
t1=t;
search1(t->l,item);
}
else if(item == t->data)
{
delete1(t);
}
}
void delete1(struct tree *t)
{
int k;
if((t->l == NULL)&& (t->r==NULL))
{
if(t1->l==t)
{
t1->l=NULL;
}
else
{
t1->r =NULL;
}
t=NULL;
delete t;
return;
}
else if((t->r == NULL))
{
if(t1 ==t)
{
root=t->l;
t1=root;
}
else if(t1->l==t)
{
t1->l=t->l;
}
else
{
t1->r=t->l;
}
t=NULL;
delete t;
return;
}
else if(t->l == NULL)
{
if(t1==t)
{
root = t->r;
t1=root;
}
else if(t1->r==t)
{
t1->r = t->r;
}
else
{
t1->l=t->r;
}
t==NULL;
delete t;
return;
}
else if((t->l !=NULL) && (t->r !=NULL))
{
t2 = root;
if(t->r !=NULL)
{
k=smallest(t->r);
}
else
{
k=largest(t->l);
}
search1(root,k);
t->data=k;
}
}
int smallest(struct tree *t)
{
t2=t;
if(t->l !=NULL)
{
t2=t;
return(smallest(t->l));
}
else
return (t->data);
}
int largest(struct tree *t)
{
if(t->r !=NULL)
{
t2=t;
return (largest(t->r));
}
else
return(t->data);
}
void display(tree *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->r, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->data;
display(ptr->l, level+1);
}
}
int main()
{
int ch;
while(1)
{
cout<<endl<<"OPERATIONS ---";
cout<<endl<<"1 - Insert element into tree"<<endl;
cout<<"2 - Delete an element from the tree"<<endl;
cout<<"3 - Inorder Traversal"<<endl;
cout<<"4 - Preorder Traversal"<<endl;
cout<<"5 - Postorder Traversal"<<endl;
cout<<"6 - Find MaxDepthn";
cout<<"7 - Display"<<endl;
cout<<"8 - Exit"<<endl;
cout<<endl<<"Enter your choice : ";
cin>>ch;
switch (ch)
{
case 1:
create();
break;
case 2:
Delete();
break;
case 3:
cout<<"printing traversal in inorder"<<endl;
inorder(root);
break;
case 4:
cout<<"printing traversal in preorder"<<endl;
preorder(root);
break;
case 5:
cout<<"printing traversal in postorder"<<endl;
postorder(root);
break;
case 6:
cout<<"Maximum depth of the binery search tree :"<<maxDepth(root)<<endl;
break;
case 7:
cout<<"Display-->"<<endl;
display(root,1);
break;
case 8:
return 0;
default :
cout<<"Wrong choice, Please enter correct choice "<<endl;
break;
}
}
getch();
return 0;
}
Corollary :-
Myprogworld 