Write a definition of the method nodeCount that returns the number of nodes in a
ID: 3763941 • Letter: W
Question
Write a definition of the method nodeCount that returns the number of nodes in a binary tree. Add this method to the class BinaryTree and test this method.
Write a definition of the method leavesCount that takes as a parameter a reference of the root node of a binary tree and returns the number of leaves in a binary tree. Add this method to the class BinaryTree and test this method.
Write a definition of the method singleP that returns the number of nodes in a binary tree that have only one child. Add this method to the class BinaryTree and test this method.
in C++
Explanation / Answer
tree :
9
/
7 7
/
5 1 3
#include <iostream>
#include <cstdlib>
#include <iostream>
using namespace std;
struct TNode{
int value;
TNode* left;
TNode* right;
TNode(){
this->value = NULL;
this->left = NULL;
this->right = NULL;
}
TNode(int value){
this->value = value;
this->left = NULL;
this->right = NULL;
}
};
class BTree{
private:
TNode *root;
TNode * aux_create_tree(int a[], int l, int r)
{
if(l>r)
return NULL;
int p=(l+r)/2;
TNode *temp = new TNode(a[p]);
temp->left=aux_create_tree(a,l,p-1);
temp->right=aux_create_tree(a,p+1,r);
return temp;
}
void aux_inorder(TNode *node)
{
if(node==NULL)
return;
aux_inorder(node->left);
cout<<node->value<<" ";
aux_inorder(node->right);
}
int aux_count(TNode *node)
{
if(node == NULL)
return 0;
return aux_count(node->left)+1+aux_count(node->right);
}
int aux_leavesCount(TNode *node)
{
if(node==NULL)
return 0;
if(node->left==NULL && node->right==NULL)
return 1;
return aux_leavesCount(node->left)+aux_leavesCount(node->right);
}
int aux_singleP(TNode *node)
{
if(node == NULL)
return 0;
if(node->left==NULL && node->right !=NULL)
return 1+aux_singleP(node->right);
if(node->left!=NULL && node->right ==NULL)
return 1+aux_singleP(node->left);
return aux_singleP(node->left)+aux_singleP(node->right);
}
public:
BTree()
{
root=NULL;
}
void create_tree(int a[],int n)
{
root = aux_create_tree(a,0,n-1);
}
void inorder()
{
aux_inorder(root);
cout<<endl;
}
int nodeCount()
{
return aux_count(root);
}
int leavesCount()
{
return aux_leavesCount(root);
}
int singleP()
{
return aux_singleP(root);
}
};
int main(){
//to demonstrate
int nums[] = { 7,5,9,1,7,3};
BTree mal;
mal.create_tree(nums,6); // store the made binary tree from nums and point it by the pointer, BinaryTree.
mal.inorder();
int count = mal.nodeCount();
cout<<"count = "<<count<<endl;
int leves = mal.leavesCount();
cout<<"number of leaves = "<<leves<<endl;
int count_single = mal.singleP();
cout<<"number of nodes with single child = "<<count_single<<endl;
}
output:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.