/*Binary search tree with all the Recursive and non Recursive traversals*/ /* By:- Aniket P. Kadu :- S.e computer :- M.E.S.C.O.E */ #include#include #include class binarynode { public: int data; binarynode *left; binarynode *right; }; class binsrctree { private: binarynode *root; void inorder_rec(binarynode *); void inorder_non_rec(binarynode *); void preorder_rec(binarynode *); void preorder_non_rec(binarynode *); void postorder_rec(binarynode *); void postorder_non_rec(binarynode *); public: binsrctree() { root=NULL; } void insert(int ); void print_inorder_rec(); void print_inorder_non_rec(); void print_preorder_rec(); void print_preorder_non_rec(); void print_postorder_rec(); void print_postorder_non_rec(); }; class stack { int top; binarynode *stackel[20]; public: stack() { top=-1; } void push(binarynode *); binarynode* pop(); int empty() { if(top==-1) return(1); return(0); } }; void stack::push(binarynode *node) { stackel[++top]=node; } binarynode *stack::pop() { return(stackel[top--]); } class stack_int { int top; int stack_int[20]; public: stack_int() { top=-1; } void push(int flag); int pop(); int empty_int() { if(top==-1) return(1); return(0); } }; void stack_int::push(int flag) { stack_int[++top]=flag; } int stack_int::pop() { return(stack_int[top--]); } /*---------------------------------------------------------------------*/ /* fUNCTION TO INSERT A NODE IN THE TREE */ /*---------------------------------------------------------------------*/ void binsrctree::insert(int val) { binarynode *temp,*prev,*curr; temp=new binarynode; temp->data=val; temp->left=temp->right=NULL; if(root==NULL) { root=temp; } else { curr=root; while(curr!=NULL) { prev=curr; if(temp->data data) curr=curr->left; else curr=curr->right; } if(temp->data data) prev->left=temp; else prev->right=temp; } } /* ------------------------------------------------*/ /*INORDER RECURSIVE TRAVERSAL*/ /*-------------------------------------------------*/ void binsrctree::inorder_rec(binarynode *root) { if(root!=NULL) { inorder_rec(root->left); cout< data<<" "; inorder_rec(root->right); } } /*--------------------------------------------------*/ /*INORDER NON RECURSIVE TRAVERSAL*/ /*--------------------------------------------------*/ void binsrctree::inorder_non_rec(binarynode *root) { stack stk; binarynode *temp; if(root!=NULL) { temp=root; do { while(temp!=NULL) { stk.push(temp); temp=temp->left; }/*end while*/ if(!stk.empty()) { temp=stk.pop(); cout< data<<" "; temp=temp->right; }/*end if*/ else break; }while(1); /*end do while*/ }/* end if */ else cout<<" Empty tree"; } /*end function */ /*--------------------------------------------------*/ /*PREORDER RECURSIVE TRAVERSAL */ /*---------------------------------------------------*/ void binsrctree::preorder_rec(binarynode *root) { if(root!=NULL) { cout< data<<" "; preorder_rec(root->left); preorder_rec(root->right); } } /*--------------------------------------------------*/ /*PREORDER NON RECURSIVE TRAVERSAL */ /*---------------------------------------------------*/ void binsrctree::preorder_non_rec(binarynode *root) { stack stk; binarynode *temp=root; stk.push(temp); while(!stk.empty()) { temp=stk.pop(); if(temp!=NULL) { cout< data<<" "; stk.push(temp->right); stk.push(temp->left); } } } /*--------------------------------------------------*/ /*POSTRDER RECURSIVE TRAVERSAL */ /*---------------------------------------------------*/ void binsrctree::postorder_rec(binarynode *root) { if(root!=NULL) { postorder_rec(root->left); postorder_rec(root->right); cout< data<<" "; } } /*--------------------------------------------------*/ /*POSTORDER NON RECURSIVE TRAVERSAL */ /*---------------------------------------------------*/ void binsrctree::postorder_non_rec(binarynode *root) { stack stk; stack_int stk1; int flag; binarynode *temp=root; do { if(temp!=NULL) { stk.push(temp); stk1.push(1); temp=temp->left; } else { if(stk.empty()) break; temp=stk.pop(); flag=stk1.pop(); if(flag==2) { cout< data; temp=NULL; } /*end if */ else { stk.push(temp); stk1.push(2); temp=temp->right; } /* end else */ } /* end if */ }while(1);/*end do while*/ }/*end function*/ /*--------------------------------------------------*/ /*FUNCTION TO PRINT INORDER RECURSIVE TRAVERSAL */ /*----------------------------------n_rec() { cout<<" "; postorder_non_rec(root); cout<<" "; } /*--------------------------------------------------*/ /* MAIN FUNCTION */ /*---------------------------------------------------*/ void main() { binsrctree BST; int ch,element; clrscr(); do { cout<<" 1.Insert a node in binary tree"; cout<<" 2.Recursive Inorder traversal"; cout<<" 3.Non Recursive Inorder traversal"; cout<<" 4.Recursive preorder traversal"; cout<<" 5.Non recursive preorder traversal"; cout<<" 6.Recursive postorder traversal"; cout<<" 7.Non recursive postorder traversal"; cout<<" 8.Exit"; cout<<" Enter your choice"; cin>>ch; switch(ch) { case 1: cout<<" Enter the element you wnat to insert"; cin>>element; BST.insert(element); break; case 2: cout<<" Recursive Inorder traversal "; BST.print_inorder_rec(); break; case 3: cout<<" NonRecursive Inorder traversal "; BST.print_inorder_non_rec(); break; case 4: cout<<" Recursive preorder traversal "; BST.print_preorder_rec(); break; case 5: cout<<" Non recursive preorder traversal "; BST.print_preorder_non_rec(); break; case 6: cout<<" Recursive postorder traversal"; BST.print_postorder_rec(); break; case 7: cout<<" Non recursive postorder traversal "; BST.print_postorder_non_rec(); break; case 8: exit(1); } }while(ch<8); } //not include below line on program//
Binary search Tree C++
Binary search tree with all the three recursive and non recursive traversals