<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 :-
You must be logged in to post a comment.