#ifndef H_binarySearchTree #define H_binarySearchTree #include #include #include "binaryTree.h" //************************************************************* // Author: D.S. Malik // // This class specifies the basic operations to implement a // binary search tree. // Revised by Dr. Ji on Npv 30 2021 //************************************************************* using namespace std; template class bSearchTreeType: public binaryTreeType { public: bool search(const elemType& searchItem) const; //Function to determine if searchItem is in the binary //search tree. //Postcondition: Returns true if searchItem is found in the // binary search tree; otherwise, returns false. void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If no node in the binary search tree has the // same info as insertItem, a node with the info insertItem // is created and inserted in the binary search tree. void deleteNode(const elemType& deleteItem); //Function to delete deleteItem from the binary search tree //Postcondition: If a node with the same info as deleteItem // is found, it is deleted from the binary search tree. private: void deleteFromTree(binaryTreeNode* &p); //Function to delete the node to which p points is deleted //from the binary search tree. //Postcondition: The node to which p points is deleted from // the binary search tree. }; template bool bSearchTreeType:: search(const elemType& searchItem) const { binaryTreeNode *current; bool found = false; if (root == NULL) cerr llink; else current = current-rlink; }//end while }//end else return found; }//end search template void bSearchTreeType::insert(const elemType& insertItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current binaryTreeNode *newNode; //pointer to create the node newNode = new binaryTreeNode; assert(newNode != NULL); newNode-info = insertItem; newNode-llink = NULL; newNode-rlink = NULL; if (root == NULL) root = newNode; else { current = root; while (current != NULL) { trailCurrent = current; if (current-info == insertItem) { cerr rlink = newNode; } }//end insert template void bSearchTreeType::deleteNode(const elemType& deleteItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current bool found = false; if (root == NULL) cout llink; else current = current-rlink; } }//end while if (current == NULL) cout rlink); }//end if } }//end deleteNode template void bSearchTreeType::deleteFromTree (binaryTreeNode* &p) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current binaryTreeNode *temp; //pointer to delete the node if (p == NULL) cerr rlink; delete temp; } else if(p-rlink == NULL) { temp = p; p = temp-llink; delete temp; } else { current = p-llink; trailCurrent = NULL; while (current-rlink != NULL) { trailCurrent = current; current = current-rlink; }//end while p-info = current-info; if (trailCurrent == NULL) //current did not move; //current == p-llink; adjust p p-llink = current-llink; else trailCurrent-rlink = current-llink; delete current; }//end else }//end deleteFromTree #endif * coUse the provided files (binarySearchTree.h and binaryTree.h) for the lab:(a) Write a recursive function, leavesCount, that takes a root node (as a pointer) of a binary tree to its function parameter.As an output of this function, you need to return the total number of leaf nodes in the tree. Define this function in theclass definition file binaryTreeType.h.int binaryTreeType:: leaves Count (binary TreeNode* p) const(b) Write a recursive function, height, that takes a root node (as a pointer) of a binary tree to its function parameter.Once it computes the height of the binary tree, return the height as a return value. Define this function in the classdefinition file binaryTreeType.h.int binaryTree Type:: height (binary TreeNode *p) const(c) Write a recursive function, swapSubtreesOfNode, that swaps all of the left and right subtrees of a binary tree. Addthis function definition to the class binaryTreeType binary Tree.h.void binaryTreeType::swapSubtreesOfNode (binary TreeNode *p)(d) Write your program satisfying the following tasks. Please note that the functions (inorder, preorder, and postorder)are defined already in the class.I(a) Creates two bSearch TreeType objects (type as in int)(b) You need to prompt the user to insert keys into the tree. Use -999 to stop inserting. The -999 must not beconsidered as inputs.(c) Print tree nodes in inorder (see screenshots)(d) Print tree nodes in preorder (see screenshots)(e) Print tree nodes in postorder (see screenshots)(f) Print the height of the tree(g) Print the number of leave nodes for the tree(h) Print tree nodes in inorder after swapping subtrees.(i) Submit all the operations' screenshots.MacBook AirD00F4F5F7F8F10F11F122$%)6

Question

#ifndef H_binarySearchTree #define H_binarySearchTree #include #include #include "binaryTree.h" //************************************************************* // Author: D.S. Malik // // This class specifies the basic operations to implement a // binary search tree. // Revised by Dr. Ji on Npv 30 2021 //************************************************************* using namespace std; template class bSearchTreeType: public binaryTreeType { public: bool search(const elemType& searchItem) const; //Function to determine if searchItem is in the binary //search tree. //Postcondition: Returns true if searchItem is found in the // binary search tree; otherwise, returns false. void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If no node in the binary search tree has the // same info as insertItem, a node with the info insertItem // is created and inserted in the binary search tree. void deleteNode(const elemType& deleteItem); //Function to delete deleteItem from the binary search tree //Postcondition: If a node with the same info as deleteItem // is found, it is deleted from the binary search tree. private: void deleteFromTree(binaryTreeNode* &p); //Function to delete the node to which p points is deleted //from the binary search tree. //Postcondition: The node to which p points is deleted from // the binary search tree. }; template bool bSearchTreeType:: search(const elemType& searchItem) const { binaryTreeNode *current; bool found = false; if (root == NULL) cerr << "Cannot search the empty tree." << endl; else { current = root; while (current != NULL && !found) { if (current->info == searchItem) found = true; else if (current->info > searchItem) current = current->llink; else current = current->rlink; }//end while }//end else return found; }//end search template void bSearchTreeType::insert(const elemType& insertItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current binaryTreeNode *newNode; //pointer to create the node newNode = new binaryTreeNode; assert(newNode != NULL); newNode->info = insertItem; newNode->llink = NULL; newNode->rlink = NULL; if (root == NULL) root = newNode; else { current = root; while (current != NULL) { trailCurrent = current; if (current->info == insertItem) { cerr << "The insert item is already in the list-"; cerr << "duplicates are not allowed." << insertItem << endl; return; } else if (current->info > insertItem) current = current->llink; else current = current->rlink; }//end while if (trailCurrent->info > insertItem) trailCurrent->llink = newNode; else trailCurrent->rlink = newNode; } }//end insert template void bSearchTreeType::deleteNode(const elemType& deleteItem) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current bool found = false; if (root == NULL) cout << "Cannot delete from the empty tree." << endl; else { current = root; trailCurrent = root; while (current != NULL && !found) { if (current->info == deleteItem) found = true; else { trailCurrent = current; if (current->info > deleteItem) current = current->llink; else current = current->rlink; } }//end while if (current == NULL) cout << "The delete item is not in the tree." << endl; else if (found) { if (current == root) deleteFromTree(root); else if (trailCurrent->info > deleteItem) deleteFromTree(trailCurrent->llink); else deleteFromTree(trailCurrent->rlink); }//end if } }//end deleteNode template void bSearchTreeType::deleteFromTree (binaryTreeNode* &p) { binaryTreeNode *current; //pointer to traverse the tree binaryTreeNode *trailCurrent; //pointer behind current binaryTreeNode *temp; //pointer to delete the node if (p == NULL) cerr << "Error: The node to be deleted is NULL." << endl; else if(p->llink == NULL && p->rlink == NULL) { temp = p; p = NULL; delete temp; } else if(p->llink == NULL) { temp = p; p = temp->rlink; delete temp; } else if(p->rlink == NULL) { temp = p; p = temp->llink; delete temp; } else { current = p->llink; trailCurrent = NULL; while (current->rlink != NULL) { trailCurrent = current; current = current->rlink; }//end while p->info = current->info; if (trailCurrent == NULL) //current did not move; //current == p->llink; adjust p p->llink = current->llink; else trailCurrent->rlink = current->llink; delete current; }//end else }//end deleteFromTree #endif * coUse the provided files (binarySearchTree.h and binaryTree.h) for the lab:(a) Write a recursive function, leavesCount, that takes a root node (as a pointer) of a binary tree to its function parameter.As an output of this function, you need to return the total number of leaf nodes in the tree. Define this function in theclass definition file binaryTreeType.h.int binaryTreeType:: leaves Count (binary TreeNode* p) const(b) Write a recursive function, height, that takes a root node (as a pointer) of a binary tree to its function parameter.Once it computes the height of the binary tree, return the height as a return value. Define this function in the classdefinition file binaryTreeType.h.int binaryTree Type:: height (binary TreeNode *p) const(c) Write a recursive function, swapSubtreesOfNode, that swaps all of the left and right subtrees of a binary tree. Addthis function definition to the class binaryTreeType binary Tree.h.void binaryTreeType::swapSubtreesOfNode (binary TreeNode *p)(d) Write your program satisfying the following tasks. Please note that the functions (inorder, preorder, and postorder)are defined already in the class.I(a) Creates two bSearch TreeType objects (type as in int)(b) You need to prompt the user to insert keys into the tree. Use -999 to stop inserting. The -999 must not beconsidered as inputs.(c) Print tree nodes in inorder (see screenshots)(d) Print tree nodes in preorder (see screenshots)(e) Print tree nodes in postorder (see screenshots)(f) Print the height of the tree(g) Print the number of leave nodes for the tree(h) Print tree nodes in inorder after swapping subtrees.(i) Submit all the operations' screenshots.MacBook AirD00F4F5F7F8F10F11F122$%)6

Accepted Answer

Java program for PreOrder Traversal:
 
import java.util.Stack;
 
public class BinaryTreePreOrder {…