Urgent C++ help!! Please design and code the following program: Using the IntBin
ID: 3836511 • Letter: U
Question
Urgent C++ help!!
Please design and code the following program:
Using the IntBinaryTree class, add the following member functions:
Leaf Counter (which counts and returns the number of leaf nodes in the tree)
Tree Height (which counts and returns the height of the tree - the height is the number of levels it contains)
Tree Width (which counts and returns the width of the tree - the width is the largest number of nodes in the same level.)
Write a simple menu-driven program that will allow the user to:
1. Insert numbers (validate for numeric)
2. Display the tree (in order)
3. Display Leaf Count
4. Display Tree Height
5. Display Tree Width
Thank you!!
Test the program as follows:
Insert the following numbers (one at a time through menu option 1): 10, 87, 9, 55, 13, 40, 22,1,0,77, 0, 4, 55, 33, 22
Display the tree
Display the leaf count
Display the tree height
Display the tree width
Explanation / Answer
#include<conio.h>
#include<process.h>
#include <cstddef>
#include<iostream>
using namespace std;
// define struct for node
struct node
{
node *left;
node *right;
int data;
} ;
// define class IntBinaryTree
class IntBinaryTree
{
public:
//staring node is root
node *root;
//constructor calling
IntBinaryTree()
{
root=NULL;
}
//checking if root equal to NULL or not
int isempty()
{
return(root==NULL);
}
//declare insert method
void insert(int item);
//declare insert method
void inordertrav();
//declare inorder method to display binary tree
void inorder(node *);
//declare method Display the tree height
int hight(node *root);
//declare method Display the leaf count
int leaf_count(node *root);
//declare method Display the width
int width(node *root);
};
//insert method definition
void IntBinaryTree::insert(int item)
{
node *temp=new node;
node *parent;
temp->data=item;
temp->left=NULL;
temp->right=NULL;
parent=NULL;
if(isempty())
root=temp;
else
{
node *ptr;
ptr=root;
while(ptr!=NULL)
{
parent=ptr;
if(item>ptr->data)
ptr=ptr->right;
else
ptr=ptr->left;
}
if(item<parent->data)
parent->left=temp;
else
parent->right=temp;
}
}
//inordertrav method definition
void IntBinaryTree::inordertrav()
{
inorder(root);
}
//inorder method definition
void IntBinaryTree::inorder(node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->left);
cout<<" "<<ptr->data<<" ";
inorder(ptr->right);
}
}
//hight method definition
int IntBinaryTree::hight(node *t)
{
if ( t == NULL) return 0;
return max( hight(t->left), hight(t->right) ) + 1;
}
//leaf_count method definition
int IntBinaryTree::leaf_count(node *temp)
{
if(temp == NULL)
return 0;
if(temp->left == NULL && temp->right==NULL)
return 1;
else
return leaf_count(temp->left)+
leaf_count(temp->right);
}
//width method definition
int IntBinaryTree::width(node *temp)
{
if (temp == NULL)
return 0;
int lheight = hight(temp->left);
int rheight = hight(temp->right);
int ldiameter = width(temp->left);
int rdiameter = width(temp->right);
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}
// main method
int main()
{
//define class object
IntBinaryTree b;
int choice;
char key;
//print menu
do{
cout << "1. Insert numbers (validate for numeric) "<<
"2. Display the tree (in order) "<<
"3. Display Leaf Count "<<
"4. Display Tree Height "<<
"5. Display Tree Width" << endl;
cout<<" Enter your Choice :";
//read choice from user
cin>>choice;
int i;
//used switch case
switch(choice)
{
case 1: //if case ==1 then insert number in binary tree
cout<<"Insert the following numbers (one at a time through menu option 1): 10, 87, 9, 55, 13, 40, 22,1,0,77, 0, 4, 55, 33, 22 :"<<endl;
b.insert(10);
b.insert(87);
b.insert(9);
b.insert(55);
b.insert(13);
b.insert(40);
b.insert(22);
b.insert(1);
b.insert(0);
b.insert(77);
b.insert(0);
b.insert(4);
b.insert(55);
b.insert(33);
b.insert(22);
break;
case 2: // if choice equal to 2 then Display the tree
cout<<" Display the tree"<<endl;
b.inordertrav();
break;
case 3: // if choice equal to 3 then Display the leaf count
cout<<" Display the leaf count : " <<b.leaf_count(b.root)<<endl;
break;
case 4: // if choice equal to 3 then Display the tree height
cout<<" Display the tree height : " << b.hight(b.root)<<endl;
break;
case 5: // if choice equal to 3 then Display the tree width
cout<<" Display the tree width : " <<b.width(b.root)<<endl;
break;
default: cout<<" Wrong Entry !! ";
}
cout<<" Do you want to continue :";
cin>>key;
}while(key=='Y' || key=='y');// while to continue print menu till request Y or y
}
-----------------------------------------------------------------------------------------------------------------------------
OutPut Sample:-
1. Insert numbers (validate for numeric)
2. Display the tree (in order)
3. Display Leaf Count
4. Display Tree Height
5. Display Tree Width
Enter your Choice :1
Insert the following numbers (one at a time through menu option 1): 10, 87, 9, 55, 13, 40, 22,1,0,77, 0, 4, 55, 33, 22 :
Do you want to continue :y
1. Insert numbers (validate for numeric)
2. Display the tree (in order)
3. Display Leaf Count
4. Display Tree Height
5. Display Tree Width
Enter your Choice :2
Display the tree
0 0 1 4 9 10 13 22 22 40 55 55 77 87
Do you want to continue :y
1. Insert numbers (validate for numeric)
2. Display the tree (in order)
3. Display Leaf Count
4. Display Tree Height
5. Display Tree Width
Enter your Choice :3
Display the leaf count : 5
Do you want to continue :y
1. Insert numbers (validate for numeric)
2. Display the tree (in order)
3. Display Leaf Count
4. Display Tree Height
5. Display Tree Width
Enter your Choice :4
Display the tree height : 7
Do you want to continue :y
1. Insert numbers (validate for numeric)
2. Display the tree (in order)
3. Display Leaf Count
4. Display Tree Height
5. Display Tree Width
Enter your Choice :5
Display the tree width : 11
Do you want to continue :n
---------------------------------------------------------------------------------------------
If you have any query, please feel free to ask.
Thanks a lot.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.