Urgent C++ help!! Please design and code the following program: Using the IntBin

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<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<stdio.h>
typedef struct node
{
int d;
struct node *l;
struct node *r;
}node;

class binarysrchtree
{
public:
node *rt;
void crt();
void insrt(node *rt,node *New);
void bfs(node *rt);
void inordr(node *rt);
int count(node *rt);
node* mirror(node *temp);
int height(node *temp);
int max(int v1,int v2);
};

void binarysrchtree::crt()

{
int count,i;
node *New;
rt=NULL;
cout<<“ Enter the number of nodes: “;
cin>>count;
for(i=0;i<count;i++)
{
New=(node*)malloc(sizeof(node));
New->l=NULL;
New->r=NULL;
cout<<“ Enter the d: “;
cin>>New->d;
if(rt==NULL)
rt=New;
else
insrt(rt,New);
}
}

void binarysrchtree::insrt(node *rt,node *New)

{
if(New->d < rt->d)
if(rt->l==NULL)
rt->l=New;
else
insrt(rt->l,New);
if(New->d > rt->d)
if(rt->r==NULL)
rt->r=New;
else
insrt(rt->r,New);
}

node* binarysrchtree::mirror(node *temp)

{
node *temp1;
if(temp==NULL)
return NULL;
else
{
temp1=temp->l;
temp->l=mirror(temp->r);
temp->r=mirror(temp1);
return temp;
}
}

void binarysrchtree::inordr(node *rt)

{
node *temp;
temp=rt;
if(temp!=NULL)
{
inordr(temp->l);
cout<<” “<<temp->d;
inordr(temp->r);
}
}

class q

{
node *d[30];
int r,f;
public:
q()
{
r=f=-1;
}

int empty()
{
if(r==-1)
return 1;
return 0;
}

void insrt(node *p)
{
if(empty())
r=f=0;
else
r=r+1;
d[r]=p;
}

node *del()
{
node *p=d[f];
if(r==f)
r=f=-1;
else
f=f+1;
return p;
}
};

void binarysrchtree::bfs(node *rt)

{
q q1;
node *temp3;
if(rt==NULL)
{
cout<<“ Tree is empty.”;
return ;
}
q1.insrt(rt);
while(!q1.empty())
{
temp3=q1.del();
if(temp3)
{
cout<<” “<<temp3->d;
if(temp3->l)
q1.insrt(temp3->l);
if(temp3->r)
q1.insrt(temp3->r);
}
else
break;
}
}

int binarysrchtree::height(node *temp)

{
if(temp==NULL)
return 0;
if(temp->l==NULL && temp->r==NULL)
return 0;
return(max(height(temp->l),height(temp->r))+1);
}

int binarysrchtree::max(int v1,int v2)

{
if(v1 > v2)
return v1;
else
return v2;
}

int binarysrchtree::count(node *rt)

{
int cnt;
node *temp2;
temp2=rt;
if(temp2==NULL)
return 0;
if(temp2->l==NULL && temp2->r==NULL)
return 1;
cnt=count(temp2->l) + count(temp2->r);
return cnt;
}

void main()

{
int ch,cnt,ht;
char ans;
binarysrchtree a;
clrscr();
cout<<“ ……OPERATIONS ON BINARY SEARCH TREE……”;
do
{
cout<<“ MENU: “;
cout<<“ 1.crt binarysrchtree 2.Display 3.Counting leaf nodes 4.BFS 5.Mirror 6.Height”;
cout<<“ Enter your choice: “;
cin>>ch;
switch(ch)
{
case 1:
a.crt();
break;
case 2:
cout<<“ inordr: “;
a.inordr(a.rt);
break;
case 3:
cnt=a.count(a.rt);
cout<<“ Number of leaf nodes: “<< cnt;
break;
case 4:
cout<<“ BFS: “;
a.bfs(a.rt);
break;
case 5:
cout<<“ Mirror Image: “;
a.mirror(a.rt);
a.inordr(a.rt);
break;
case 6:
ht=a.height(a.rt);
cout<<“ Height of the tree: “<< ht;
break;
}
cout<<“ Do you want to continue?(y/n): “;
fflush(stdin);
cin>>ans;
}while(ans==’y’ || ans==’Y’);
getch();
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.