Write a Program of Binary Search Tree Operations.
#include <iostream.h> #include <process.h> //for exit(1) #include <conio.h> struct node{ int data; struct node *left; struct node *right; }; class BST{ public: node *tree; BST(){ tree=NULL; } void createTree(node **,int item); //For Building Treevoid preOrder(node *); //For Tree Traversalvoid inOrder(node *); void postOrder(node *); void determineHeight(node *,int *); int totalNodes(node *); int internalNodes(node *); //no. of non-leaf nodesint externalNodes(node *); //no. of leaf nodes.void removeTree(node **); //Remove tree from memory. node **searchElement(node **,int); void findSmallestNode(node *); void findLargestNode(node *); void deleteNode(int); }; //it is used for inseting an single element in//a tree, but if calls more than once will create tree.void BST :: createTree(node **tree,int item){ if(*tree == NULL){ *tree = new node; (*tree)->data = item; (*tree)->left = NULL; (*tree)->right = NULL; } else{ if( (*tree)->data > item) createTree( &((*tree)->left),item); else createTree( &((*tree)->right),item); } } void BST :: preOrder(node *tree){ if( tree!=NULL){ cout<<" "<< tree->data; preOrder(tree->left); preOrder(tree->right); } } void BST :: inOrder(node *tree){ if( tree!=NULL){ inOrder( tree->left); cout<<" "<< tree->data; inOrder(tree->right); } } void BST :: postOrder(node *tree){ if( tree!=NULL){ postOrder( tree->left); postOrder( tree->right); cout<<" "<<tree->data; } } void BST :: determineHeight(node *tree, int *height){ int left_height, right_height; if( tree == NULL) *height = 0; else{ determineHeight(tree->left, &left_height); determineHeight(tree->right, &right_height); if( left_height > right_height) *height = left_height + 1; else *height = right_height + 1; } } int BST :: totalNodes(node *tree){ if( tree == NULL) return 0; elsereturn( totalNodes(tree->left) + totalNodes(tree->right) + 1 ); } int BST :: internalNodes(node *tree){ if( (tree==NULL) || (tree->left==NULL && tree->right==NULL)) return 0; elsereturn( internalNodes(tree->left) + internalNodes(tree->right) + 1 ); } int BST :: externalNodes(node *tree){ if( tree==NULL ) return 0; elseif( tree->left==NULL && tree->right==NULL) return 1; elsereturn( externalNodes(tree->left) + externalNodes(tree->right)); } void BST :: removeTree(node **tree){ if( (*tree) != NULL){ removeTree( &(*tree)->left ); removeTree( &(*tree)->right ); delete( *tree ); } } node ** BST :: searchElement(node **tree, int item){ if( ((*tree)->data == item) || ( (*tree) == NULL) ) return tree; elseif( item < (*tree)->data) return searchElement( &(*tree)->left, item); elsereturn searchElement( &(*tree)->right, item); } void BST :: findSmallestNode(node *tree){ if( tree==NULL || tree->left==NULL) cout<< tree->data; else findSmallestNode( tree->left); } //Finding In_order Successor of given node..//for Delete Algo. node * find_Insucc(node *curr) { node *succ=curr->right; //Move to the right sub-tree.if(succ!=NULL){ while(succ->left!=NULL) //If right sub-tree is not empty. succ=succ->left; //move to the left-most end. } return(succ); } void BST :: findLargestNode(node *tree){ if( tree==NULL || tree->right==NULL) cout<<tree->data; else findLargestNode(tree->right); } void BST :: deleteNode(int item){ node *curr=tree,*succ,*pred; int flag=0,delcase; //step to find location of nodewhile(curr!=NULL && flag!=1) { if(item < curr->data){ pred = curr; curr = curr->left; } elseif(item > curr->data){ pred = curr; curr = curr->right; } else{ //curr->data = item flag=1; } } if(flag==0){ cout<<"\nItem does not exist : No deletion\n"; getch(); goto end; } //Decide the case of deletionif(curr->left==NULL && curr->right==NULL) delcase=1; //Node has no childelseif(curr->left!=NULL && curr->right!=NULL) delcase=3; //Node contains both the childelse delcase=2; //Node contains only one child//Deletion Case 1if(delcase==1){ if(pred->left == curr) //if the node is a left child pred->left=NULL; //set pointer of its parentelse pred->right=NULL; delete(curr); //Return deleted node to the memory bank. } //Deletion Case 2if(delcase==2){ if(pred->left==curr){ //if the node is a left childif(curr->left==NULL) pred->left=curr->right; else pred->left=curr->left; } else{ //pred->right=currif(curr->left==NULL) pred->right=curr->right; else pred->right=curr->left; } delete(curr); } //Deletion case 3if(delcase==3){ succ = find_Insucc(curr); //Find the in_order successor//of the node.int item1 = succ->data; deleteNode(item1); //Delete the inorder successor curr->data = item1; //Replace the data with the data of//in order successor. } end: } void main(){ BST obj; int choice; int height=0,total=0,n,item; node **tmp; while(1){ clrscr(); cout<<"*****BINARY SEARCH TREE OPERATIONS*****\n\n"; cout<<"--Binary Tree and Binary Search Tree common operations--\n"; cout<<"1) Create Tree\n"; cout<<"2) Traversal\n"; cout<<"3) Height of Tree\n"; cout<<"4) Total Nodes\n"; cout<<"5) Internal Nodes \n"; cout<<"6) External Nodes \n"; cout<<"7) Remove Tree\n"; cout<<"\n--Only Binary Search Tree Operations--\n"; cout<<"8) Insert Node\n"; cout<<"9) Search Node\n"; cout<<"10) Find Smallest Node\n"; cout<<"11) Find Largest Node\n"; cout<<"12) Delete Node\n"; cout<<"13) Exit\n"; cout<<"Enter your choice : "; cin>>choice; switch(choice){ case 1 : //Create Tree cout<<"\n\n--Creating Tree--"; cout<<"\nHow many nodes u want to enter : "; cin>>n; for(int i=0;i<n;i++){ cout<<"Enter value : "; cin>>item; obj.createTree(&obj.tree,item); } break; case 2 : //All Traversals cout<<"\n\nInorder Traversal : "; obj.inOrder(obj.tree); cout<<"\n\nPre-order Traversal : "; obj.preOrder(obj.tree); cout<<"\n\nPost-order Traversal : "; obj.postOrder(obj.tree); getch(); break; case 3 : //Determining Height of Tree obj.determineHeight(obj.tree,&height); cout<<"\n\nHeight of Tree : "<<height; getch(); break; case 4 : //Total nodes in a tree total=obj.totalNodes(obj.tree); cout<<"\n\nTotal Nodes : "<<total; getch(); break; case 5 : //Internal nodes in a tree total=obj.internalNodes(obj.tree); cout<<"\n\nInternal Nodes : "<<total; getch(); break; case 6 : //External nodes in a tree total=obj.externalNodes(obj.tree); cout<<"\n\nExternal Nodes : "<<total; getch(); break; case 7 : //Remove Tree from memory obj.removeTree(&obj.tree); cout<<"\n\nTree is removed from Memory"; getch(); break; case 8 : //Inserting a node in a tree cout<<"\n\n--Inserting Node in a tree--\n"; cout<<"Enter value : "; cin>>item; obj.createTree(&obj.tree,item); cout<<"\nItem is inserted\n"; getch(); break; case 9 : //Search element cout<<"\n\n--Search Element--\n"; cout<<"Enter item to searched : "; cin>>item; &(*tmp) = obj.searchElement(&obj.tree,item); if( (*tmp) == NULL) cout<<"\nSearch Element Not Found"; else cout<<"\nSearch Element was Found"; getch(); break; case 10 : //Find Smallest Node cout<<"\n\nSmallest Node is : "; obj.findSmallestNode(obj.tree); getch(); break; case 11 : //Find Largest Node cout<<"\n\nLargest Node is : "; obj.findLargestNode(obj.tree); getch(); break; case 12 : //Deleting a node from a tree cout<<"\n\n--Deleting a Node from a tree--\n"; cout<<"Enter value : "; cin>>item; obj.deleteNode(item); break; case 13 : exit(1); }//end of switch } }
