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. };

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
  • 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.

    };

binarySearchTree.h
1
//Header File Binary Search Tree
2.
3
#ifndef H_binarySearchTree
4
#define H_binarySearchTree
#include <iostream>
6
#include "binaryTree.h"
7
8
using namespace std;
9
10
template <class elemType>
11
class bSearchTreeType: public binaryTreeType<elemType>
12
{
13
public:
14
bool search(const elemType& searchItem) const;
15
//Function to determine if searchItem is in the binary
16
//search tree.
17
//Postcondition: Returns true if searchItem is found in
18
//
the binary search tree; otherwise,
19
//
returns false.
20
void insert(const elemType& insertItem);
//Function to insert insertItem in the binary search tree.
//Postcondition: If there is no node in the binary search
21
22
23
24
//
tree that has the same info as
25
//
insertItem, a node with the info
insertItem is created and inserted in the
26
//
27
//
binary search tree.
28
void deleteNode (const elemType& deleteItem);
29
30
//Function to delete deleteItem from the binary search tree
31
//Postcondition: If a node with the same info as deleteItem
32
//
is found, it is deleted from the binary
33
//
search tree.
If the binary tree is empty or deleteItem
is not in the binary tree, an appropriate
message is printed.
34
//
35
//
36
//
37
38
private:
39
void deleteFromTree(nodeType<elemType>* &p);
40
//Function to delete the node to which p points is
41
//deleted from the binary search tree.
42
//Postcondition: The node to which p points is deleted
43
//
from the binary search tree.
44
};
45
Transcribed Image Text:binarySearchTree.h 1 //Header File Binary Search Tree 2. 3 #ifndef H_binarySearchTree 4 #define H_binarySearchTree #include <iostream> 6 #include "binaryTree.h" 7 8 using namespace std; 9 10 template <class elemType> 11 class bSearchTreeType: public binaryTreeType<elemType> 12 { 13 public: 14 bool search(const elemType& searchItem) const; 15 //Function to determine if searchItem is in the binary 16 //search tree. 17 //Postcondition: Returns true if searchItem is found in 18 // the binary search tree; otherwise, 19 // returns false. 20 void insert(const elemType& insertItem); //Function to insert insertItem in the binary search tree. //Postcondition: If there is no node in the binary search 21 22 23 24 // tree that has the same info as 25 // insertItem, a node with the info insertItem is created and inserted in the 26 // 27 // binary search tree. 28 void deleteNode (const elemType& deleteItem); 29 30 //Function to delete deleteItem from the binary search tree 31 //Postcondition: If a node with the same info as deleteItem 32 // is found, it is deleted from the binary 33 // search tree. If the binary tree is empty or deleteItem is not in the binary tree, an appropriate message is printed. 34 // 35 // 36 // 37 38 private: 39 void deleteFromTree(nodeType<elemType>* &p); 40 //Function to delete the node to which p points is 41 //deleted from the binary search tree. 42 //Postcondition: The node to which p points is deleted 43 // from the binary search tree. 44 }; 45
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

Blurred answer
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education