C++ Data Structures (Binary Trees)- 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. Here are the headers: binaryTree.h //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; 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. binaryTreeType(const binaryTreeType& otherTree); //Copy constructor binaryTreeType(); //Default constructor ~binaryTreeType(); //Destructor 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 = 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. };
-
C++ Data Structures (Binary Trees)- 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. Here are the headers:
binaryTree.h
//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree
#include <iostream>
using namespace std;
//Definition of the Node
template <class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *lLink;
nodeType<elemType> *rLink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//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.
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//Copy constructor
binaryTreeType();
//Default constructor
~binaryTreeType();
//Destructor
protected:
nodeType<elemType> *root;
private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* 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<elemType>* &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<elemType> *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<elemType> *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<elemType> *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<elemType> *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<elemType> *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<elemType> *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.
};
Trending now
This is a popular solution!
Step by step
Solved in 2 steps