Write the definition of the function, nodeCount, that returns the number of node
ID: 3656534 • Letter: W
Question
Write the definition of the function, nodeCount, that returns the number of nodes in a binary tree. Add this function to the class binaryTreeType and create a program to test this function.Explanation / Answer
#ifndef H_binaryTree#define H_binaryTree#include using namespace std;//Definition of the Nodetemplate struct nodeType{ elemType info; nodeType *lLink; nodeType *rLink;};//Definition of the classtemplate class binaryTreeType{public:const binaryTreeType& operator= (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 = NULL; 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& otherTree);//Copy constructor binaryTreeType();//Default constructor ~binaryTreeType();//Destructor void swapSubtreeNodes();void swapSubtreeNodes(nodeType *p);void printTree(nodeType *p);void print();protected: nodeType *root;private:void copyTree(nodeType* &copiedTreeRoot, nodeType* otherTreeRoot);//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* &p);//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 = NULL; void inorder(nodeType *p) const;//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 *p) const;//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 *p) const;//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 *p) const;//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 *p) const;//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 *p) const;//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.};//Definition of member functionstemplate binaryTreeType::binaryTreeType(){ root = NULL;}template bool binaryTreeType::isEmpty() const{return (root == NULL);}template void binaryTreeType::inorderTraversal() const{ inorder(root);}template void binaryTreeType::preorderTraversal() const{ preorder(root);}template void binaryTreeType::postorderTraversal() const{ postorder(root);}template int binaryTreeType::treeHeight() const{return height(root);}template int binaryTreeType::treeNodeCount() const{return nodeCount(root);}template int binaryTreeType::treeLeavesCount() const{return leavesCount(root);}template void binaryTreeType::copyTree (nodeType* &copiedTreeRoot, nodeType* otherTreeRoot){if (otherTreeRoot == NULL) copiedTreeRoot = NULL;else { copiedTreeRoot = new nodeType; copiedTreeRoot->info = otherTreeRoot->info; copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink); copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink); }} //end copyTreetemplate void binaryTreeType::inorder (nodeType *p) const{if (p != NULL) { inorder(p->lLink); cout lLink); postorder(p->rLink); cout rLink);delete p; p = NULL; }}template void binaryTreeType::destroyTree(){ destroy(root);}//copy constructortemplate binaryTreeType::binaryTreeType (const binaryTreeType& otherTree){if (otherTree.root == NULL) //otherTree is empty root = NULL;else copyTree(root, otherTree.root);}//Destructortemplate binaryTreeType::~binaryTreeType(){ destroy(root);}templateint binaryTreeType::height (nodeType *p) const{if (p == NULL)return 0;elsereturn 1 + max(height(p->lLink), height(p->rLink));}template int binaryTreeType::max(int x, int y) const{if (x >= y)return x;elsereturn y;}template int binaryTreeType::nodeCount(nodeType *p) const{ cout rlink = temp; } root = temp; }template void binaryTreeType::insert (const elemType& insertItem){ nodeType *current; //pointer to traverse the tree nodeType *trailCurrent; //pointer behind current nodeType *newNode; //pointer to create the node newNode = new nodeType; 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) { cout info > insertItem) trailCurrent->lLink = newNode;else trailCurrent->rLink = newNode; }}//end inserttemplatevoid binaryTreeType::printTree(nodeType *p){if (p == NULL) return; printTree(p->left); printf("%d ", p->data); printTree(p->right);}templatevoid binaryTreeType::print(){ print();}#endifRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.