Question
//Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree #include using namespace std; //Definition of the Node template struct nodeType { elemType info; nodeType *lLink;
//Header File Binary Search Tree #ifndef H_binaryTree #define H_binaryTree
#include
using namespace std; //Definition of the Node template
bool isEmpty() const; //Function to determine whether the binary tree is empty. //Postcondition: Returns true if the binary tree is empty; // otherwise, returns false.
void inorderTraversal() const; //Function to do an inorder traversal of the binary tree. //Postcondition: Nodes are printed in inorder sequence.
void preorderTraversal() const; //Function to do a preorder traversal of the binary tree. //Postcondition: Nodes are printed in preorder sequence.
void postorderTraversal() const; //Function to do a postorder traversal of the binary tree. //Postcondition: Nodes are printed in postorder sequence.
int treeHeight() const; //Function to determine the height of a binary tree. //Postcondition: Returns the height of the binary tree.
int treeNodeCount() const; //Function to determine the number of nodes in a //binary tree. //Postcondition: Returns the number of nodes in the // binary tree.
int treeLeavesCount() const; //Function to determine the number of leaves in a //binary tree. //Postcondition: Returns the number of leaves in the // binary tree.
void destroyTree(); //Function to destroy the binary tree. //Postcondition: Memory space occupied by each node // is deallocated. // root = nullptr;
virtual bool search(const elemType& searchItem) const = 0; //Function to determine if searchItem is in the binary //tree. //Postcondition: Returns true if searchItem is found in // the binary tree; otherwise, returns // false.
virtual void insert(const elemType& insertItem) = 0; //Function to insert insertItem in the binary tree. //Postcondition: If there is no node in the binary tree // that has the same info as insertItem, a // node with the info insertItem is created // and inserted in the binary search tree.
virtual void deleteNode(const elemType& deleteItem) = 0; //Function to delete deleteItem from the binary tree //Postcondition: If a node with the same info as // deleteItem is found, it is deleted from // the binary tree. // If the binary tree is empty or // deleteItem is not in the binary tree, // an appropriate message is printed.
binaryTreeType(const binaryTreeType
binaryTreeType(); //Default constructor
~binaryTreeType(); //Destructor
protected: nodeType
private: void copyTree(nodeType
void destroy(nodeType
void inorder(nodeType
void preorder(nodeType
void postorder(nodeType
int height(nodeType
int max(int x, int y) const; //Function to determine the larger of x and y. //Postcondition: Returns the larger of x and y.
int nodeCount(nodeType
int leavesCount(nodeType
//Definition of member functions
template
template
template
template
template
template
template
template
template
template
template
template
//Overload the assignment operator template
if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); }//end else
return *this; }
template
template
//copy constructor template
//Destructor template
template
template
template
return 0; }
template
if(p == nullptr) return 0; if(p->llink == nullptr && rlink == nullptr) return 1; else return leavesCount(p->llink) + leavesCount(p->rlink); }
#endif
//Header File Binary Search Tree
#pragma once #include
template
void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If there is no node in the binary search // tree that 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. // If the binary tree is empty or deleteItem // is not in the binary tree, an appropriate // message is printed.
private: void deleteFromTree(nodeType
template
if (root == nullptr) cout << "Cannot search an empty tree." << endl; else { current = root;
while (current != nullptr && !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
newNode = new nodeType
if (root == nullptr) root = newNode; else { current = root; while (current != nullptr) { trailCurrent = current;
if (current->info == insertItem) { cout << "The item to be inserted is already "; cout << "in the tree -- duplicates are not " << "allowed." << 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
if (root == nullptr) cout << "Cannot delete from an empty tree." << endl; else { current = root; trailCurrent = root;
while (current != nullptr && !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 == nullptr) cout << "The item to be deleted 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); } else cout << "The item to be deleted is not in the tree." << endl; } } //end deleteNode
template
if (p == nullptr) cout << "Error: The node to be deleted does not exist." << endl; else if (p->lLink == nullptr && p->rLink == nullptr) { temp = p; p = nullptr; delete temp; } else if (p->lLink == nullptr) { temp = p; p = temp->rLink; delete temp; } else if (p->rLink == nullptr) { temp = p; p = temp->lLink; delete temp; } else { current = p->lLink; trailCurrent = nullptr;
while (current->rLink != nullptr) { trailCurrent = current; current = current->rLink; }//end while
p->info = current->info;
if (trailCurrent == nullptr) //current did not move; //current == p->lLink; adjust p p->lLink = current->lLink; else trailCurrent->rLink = current->lLink; delete current; }//end else } //end deleteFromTree
#include
using namespace std;
int main() { return 0; }
solve the code
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started