1. Write the definition of the function nodeCount that returns the number of nodes in the binary...
Question:
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 the class binaryTreeType and create a program to test this function.
struct binaryTreeNode
{
int info;
binaryTreeNode *llink;
binaryTreeNode *rlink;
};
class binaryTreeType
{
public:
//const binaryTreeTypeint& operator= (const binaryTreeTypeint&);
bool isEmpty() const;
void inorderTrav() ;
void preorderTrav() ;
void postorderTrav() ;
void insert(int& insertItem);
binaryTreeType();//default
protected:
binaryTreeNode *root;
private:
void inorder(binaryTreeNode *p) ;
void preorder(binaryTreeNode *p) ;
void postorder(binaryTreeNode *p) ;
int nodecount();
int leavescount();
};
//binTree.cpp file
#include
#include
using namespace std;
#include"binTree.h"
bool binaryTreeType::isEmpty()const
{
return(root==NULL);
}
binaryTreeType::binaryTreeType()
{
root=NULL;
}
void binaryTreeType::inorderTrav()
{
inorder(root);
}
void binaryTreeType::preorderTrav()
{
preorder(root);
}
void binaryTreeType::postorderTrav()
{
postorder(root);
}
int nodecount()
{
return nodecount();
}
int leavescount()
{
return leavescount();
}
void binaryTreeType::inorder(binaryTreeNode *p)
{
if(p!=NULL)
{
inorder(p->llink);
cout<info<<" ";
inorder(p->rlink);
}//end if
}
void binaryTreeType::preorder(binaryTreeNode *p)
{
if(p!=NULL)
{
cout<info<<" ";
preorder(p->llink);
preorder(p->rlink);
}//end if
}
void binaryTreeType::postorder(binaryTreeNode *p)
{
if(p!=NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout<info<<" ";
}//end if
}
void binaryTreeType::insert( int& insertItem)
{
binaryTreeNode *current;
binaryTreeNode *trailCurrent;
binaryTreeNode *newNode;
newNode=new binaryTreeNode;
//assert(newNode!=NULL);
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<<"The insert item is already in the tree, no duplicates "<
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 else
}//end insert
int nodecount(binaryTreeNode *node)
{
if(root==NULL)
return 0;
else
return(1+(nodecount(l->link)+nodecount(r->link));
}
int leafcount(binaryTreeNode *node)
{
if(root==NULL)
return 0;
if(node->llink==NULL && node->rlink==NULL)
return 1;
else
return(1+ (leafcount(l->link)+leafcount(r->link));
}
---------------------------------------------------------------------------------------------------------------
//main
#include
#include
using namespace std;
#include"binTree.h"
int main()
{
binaryTreeType tree;
int num;
int i;
for(i=0;i<7;i++)
{
cout<<"Enter a #: ";
cin>>num;
tree.insert(num);
}
cout<
cout<<"Tree nodes inorder: ";
tree.inorderTrav();
cout<
cout<<"Tree nodes preorder: ";
tree.preorderTrav();
cout<
cout<<"Tree nodes postorder: ";
tree.postorderTrav();
cout << endl;
cout<<”Node count: “;
tree.nodecount();
cout<
cout<<”Leaf count: “;
tree.leavescount();
cout<
system("PAUSE");
return 0;
}