Question
Write a version of the preorder traversal algorithm in which a user-defined function can be passed as a parameter to specify the visiting criteria at
Write a version of the preorder traversal algorithm in which a user-defined function can be passed as a parameter to specify the visiting criteria at a node. Note: Methods preorderTraversal and preorder will need to be overloaded. The signature for the overloaded methods is provided in binaryTree.h below: //binaryTree.h //Header File Binary Tree #ifndef H_binaryTree #define H_binaryTree #include using namespace std; //Definition of the node template struct nodeType { elemType info; nodeType *lLink; nodeType *rLink; }; //Definition of the class template 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 = 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. // // ////new code from private to public void swapSubtrees(); //Initially incorrect placement! // void swapSubtrees(nodeType *p) const; //void swapSubtrees() const; binaryTreeType(const binaryTreeType& otherTree); //Copy constructor binaryTreeType(); //Default constructor ~binaryTreeType(); //Destructor protected: nodeType *root; private: //New Code - was missing! void swapSubtreesOfNode(nodeType *p); 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 = nullptr; 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. ////new code // void swapSubtrees(nodeType *p) const; // void swapSubtrees() const; }; //New Code template void binaryTreeType::swapSubtrees() //void binaryTreeType::swapSubtrees() const //Call the function { swapSubtreesOfNode(root); }//End function ////Function definition OF SWAPSUBTREESOFNODE!! template void binaryTreeType::swapSubtreesOfNode(nodeType *p) { nodeType *temp; //Swap the nodes if(p != nullptr) { temp = p->lLink; p->lLink = p->rLink; p->rLink = temp; swapSubtreesOfNode(p->lLink); swapSubtreesOfNode(p->rLink); }//End } /*INCORRECT { nodeType *temp; if (p!=nullptr) { temp = p->lLink; p->lLink = p->rlink; p->rLink = temp; swapSubtrees(p->lLink); swapSubtrees(p->rLink); } } */ template bool binaryTreeType::isEmpty() const { return (root == nullptr); } template binaryTreeType::binaryTreeType() { root = nullptr; } 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::inorder (nodeType *p) const { if (p != nullptr) { inorder(p->lLink); cout << p->info << " "; inorder(p->rLink); } } template void binaryTreeType::preorder (nodeType *p) const { if (p != nullptr) { cout << p->info << " "; preorder(p->lLink); preorder(p->rLink); } } template void binaryTreeType::postorder (nodeType *p) const { if (p != nullptr) { postorder(p->lLink); postorder(p->rLink); cout << p->info << " "; } } template int binaryTreeType::height (nodeType *p) const { if (p == nullptr) return 0; else return 1 + max(height(p->lLink), height(p->rLink)); } template int binaryTreeType::max(int x, int y) const { if (x >= y) return x; else return y; } template void binaryTreeType::copyTree (nodeType* &copiedTreeRoot, nodeType* otherTreeRoot) { 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::destroy(nodeType* &p) { if (p != nullptr) { destroy(p->lLink); destroy(p->rLink); delete p; p = nullptr; } } template void binaryTreeType::destroyTree() { destroy(root); } //copy constructor template binaryTreeType::binaryTreeType (const binaryTreeType& otherTree) { if (otherTree.root == nullptr) //otherTree is empty root = nullptr; else copyTree(root, otherTree.root); } //Destructor template binaryTreeType::~binaryTreeType() { destroy(root); } //Overload the assignment operator template const binaryTreeType& binaryTreeType:: operator=(const binaryTreeType& otherTree) { 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 int binaryTreeType::nodeCount(nodeType *p) const { if(p==NULL) return 0; else return 1 + nodeCount(p -> lLink) + nodeCount(p->rLink); } #endif
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