Question: C++ chapter 19 Binary Trees 1. Write the definition of the function, nodeCount, that returns the number of nodes in the binary tree. Add this
C++ chapter 19 Binary Trees
1. Write the definition of the function, nodeCount, that returns the number of nodes in the binary tree. Add this function to the class binaryTreeType and create a program to test this function.
2. Write the definition of the function, leavesCount, that takes as a parameter a pointer to the root node of a binary tree and returns the number of leaves in a binary tree. Add this function to theclass binaryTreeType and create a program to test this function.
3. Write a function, swapSubtrees, that swaps all of the left and right subtrees of a binary tree. Add this function to the class binaryTreeType and create a program to test this function.
Complete Programming Exercise 1, 2, and 3. The exercises yield to one solution. Use the test scenario I have included below to test your program. Take a screenshot of your output and include it with your solution.
The output should be like below:
The sample of Output
Enter the element ending with -1
9
6
2
4
98
5
5
The item to be inserted is already in the tree - - duplicate are not allowed.
96
-1
The elements in the order:2 3 4 5 9 96 98
The number of nodes in the binary tree:8
The number of leaves in the binary tree:2
The tree height is 6
After swapping subtrees the tree elements i n order:98 96 9 6 5 4 3 2
Tree height: 6
Here is my program:
main.c:
#include
#include "binarySearchTree.h"
using namespace std;
int main()
{
bSearchTreeType
int num;
cout << "Enter integers ending with -1 "< cin>>num; while (num != -1) { treeRoot.insert(num); cin >> num; } cout << endl << "Tree nodes in inorder: "; treeRoot.inorderTraversal(); cout << "Tree Height: " << treeRoot.treeHeight() << endl; cout << "Number of Nodes: " << treeRoot.treeNodeCount() << endl; cout << "Number of Leaves: " << treeRoot.treeLeavesCount() << endl; cout << "Tree Height: " << treeRoot.treeHeight() << endl; treeRoot.swapSubtress(); cout<<"After swaping subtress the tree element in inorder:"< treeRoot.inorderTraversal(); cout << endl; cout << "Tree Height: " << treeRoot.treeHeight() << endl; return 0; } binaryTree.h #ifndef H_binaryTree #define H_binaryTree #include using namespace std; //Definition of the Node template struct nodeType { elemType info; nodeType nodeType }; //Definition of the class template class binaryTreeType { public: const binaryTreeType (const binaryTreeType //Overload the assignment operator. 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. void swapSubtrees(); binaryTreeType(const binaryTreeType //Copy constructor binaryTreeType(); //Default constructor ~binaryTreeType(); //Destructor protected: nodeType private: void copyTree(nodeType nodeType //Makes a copy of the binary tree to which //otherTreeRoot points. //Postcondition: The pointer copiedTreeRoot points to // the root of the copied binary tree. void destroy(nodeType //Function to destroy the binary tree to which p points. //Postcondition: Memory space occupied by each node, in // the binary tree to which p points, is // deallocated. // p = nullptr; void inorder(nodeType //Function to do an inorder traversal of the binary //tree to which p points. //Postcondition: Nodes of the binary tree, to which p // points, are printed in inorder sequence. void preorder(nodeType //Function to do a preorder traversal of the binary //tree to which p points. //Postcondition: Nodes of the binary tree, to which p // points, are printed in preorder // sequence. void postorder(nodeType //Function to do a postorder traversal of the binary //tree to which p points. //Postcondition: Nodes of the binary tree, to which p // points, are printed in postorder // sequence. int height(nodeType //Function to determine the height of the binary tree //to which p points. //Postcondition: Height of the binary tree to which // p points is returned. 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 //Function to determine the number of nodes in //the binary tree to which p points. //Postcondition: The number of nodes in the binary // tree to which p points is returned. int leavesCount(nodeType // ToDo : declare leavesCount() here: //Function to determine the number of leaves in //the binary tree to which p points //Postcondition: The number of leaves in the binary // tree to which p points is returned. void swapSubtreesOfNode(nodeType //Definition of member functions template binaryTreeType { root = nullptr; } template bool binaryTreeType { return (root == nullptr); } template void binaryTreeType { inorder(root); } template void binaryTreeType { preorder(root); } template void binaryTreeType { postorder(root); } template int binaryTreeType { return height(root); } template int binaryTreeType { return nodeCount(root); } template int binaryTreeType { return leavesCount(root); } template void binaryTreeType (nodeType nodeType { if (otherTreeRoot == nullptr) copiedTreeRoot = nullptr; else { copiedTreeRoot = new nodeType copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink); copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink); } } //end copyTree template void binaryTreeType (nodeType { if (p != nullptr) { inorder(p->lLink); cout << p->info << " "; inorder(p->rLink); } } template void binaryTreeType (nodeType { if (p != nullptr) { cout << p->info << " "; preorder(p->lLink); preorder(p->rLink); } } template void binaryTreeType (nodeType { if (p != nullptr) { postorder(p->lLink); postorder(p->rLink); cout << p->info << " "; } } //Overload the assignment operator template const binaryTreeType operator=(const binaryTreeType { if (this != &otherTree) //avoid self-copy { if (root != nullptr) //if the binary tree is not empty, //destroy the binary tree destroy(root); if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); }//end else return *this; } template void binaryTreeType { if (p != nullptr) { destroy(p->lLink); destroy(p->rLink); delete p; p = nullptr; } } template void binaryTreeType { destroy(root); } //copy constructor template binaryTreeType (const binaryTreeType { if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); } //Destructor template binaryTreeType { destroy(root); } template int binaryTreeType (nodeType { if (p == nullptr) return 0; else return 1 + max(height(p->lLink), height(p->rLink)); } template int binaryTreeType { if (x >= y) return x; else return y; } // ToDo : implement the member template function // nodeCount() here. Name the template class parameter // 'elemType' . Have nodeCount() take one parameter, a // nodeType // The logic will be recursive, containing two calls to // itself. // ToDo : implement the member template function // leavesCount() here. Name the template class parameter // 'elemType' . Have leavesCount() take a nodeType // and return an int. The logic will be recursive, containing // two calls to itself. template int binaryTreeType (nodeType { if (p == nullptr) return 0; else return 1 + nodeCount(p->lLink) + nodeCount(p->rLink); } template int binaryTreeType (nodeType { if (p == nullptr) return 0; if(p->lLink==nullptr && p->rLink==nullptr) return 1; else return leavesCount(p->lLink) + leavesCount(p->rLink); } #endif binarySearchTree.h: #ifndef H_binarySearchTree #define H_binarySearchTree #include #include "binaryTree.h" 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 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 //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 (const elemType& searchItem) const { nodeType bool found = false; if (this->root == nullptr) cout << "Cannot search an empty tree." << endl; else { current = this->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 void bSearchTreeType (const elemType& insertItem) { nodeType nodeType //behind current nodeType newNode = new nodeType newNode->info = insertItem; newNode->lLink = nullptr; newNode->rLink = nullptr; if (this->root == nullptr) this->root = newNode; else { current = this->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 void bSearchTreeType (const elemType& deleteItem) { nodeType nodeType bool found = false; if (this->root == nullptr) cout << "Cannot delete from an empty tree." << endl; else { current = this->root; trailCurrent = this->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 == this->root) deleteFromTree(this->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 void bSearchTreeType (nodeType { nodeType nodeType nodeType 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 #endif It supposed to swap> but here in my program is not swapping can you please check.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help