Compute this in C++ Write a C++ program that implements a binary search tree (BS

Question

Compute this in C++ Write a C++ program that implements a binary search tree (BST) to manage a number of integer items with different priorities. In order to do so, you will need to maintain a queue as an item in the tree. Each queue item is an integer. All items in a given queue will have the same priority. As a new item with a user-specified priority comes in. it should be enqueued in the queue with items of that, priority. A new queue may need to created in case a queue with that priority does not exist. Use dynamic memory to manage nodes in the queue and BST. Absolutely no global variables anywhere in your code! Implement the following: (a) Constructor. (b) Destructor. (c) Overloaded copy constructor. (d) Overloaded assignment operator. (e) Overloaded "==" operator to check if two trees are equal. A tree t1 is equal to t2 if for every queue in t1, a corresponding queue with the same priority exists in t2 with the same set of elements (the order of the elements in the queue den's not matter). (f) Overloaded "

Explanation / Answer

#include #include //for exit(1) #include 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){ coutleft); coutright); cout 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) coutleft); } //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) coutright); } 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 data){ pred = curr; curr = curr->left; } elseif(item > curr->data){ pred = curr; curr = curr->right; } else{ //curr->data = item flag=1; } } if(flag==0){ coutright==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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.