Description: Create a class called BinSearchTree. BinSearchTree will implement a
ID: 3551742 • Letter: D
Question
Description: Create a class called BinSearchTree. BinSearchTree will implement a binary search tree. BinSearchTree will be a generic class storing a value of the generic type. It should have the following methods. The methods should all operate on the object making the call (none are static). 10 points a) add Adds a node to the tree containing the passed value. 10 points b) find Returns true if the value passed is in the tree. 10 points c) leafCount Returns the count of all of the leaves in the tree. 10 points d) height Returns the height of the tree. 10 points e) balance Rebuilds the tree to minimum height. 10 points f) isPerfect Returns true if the tree is a perfect tree. (A perfect tree is filled at every level). 10 points g) numLevels Returns the number of levels in the tree. 10 points h) isMirror Returns true if the left subtree structure is a mirror of the right subtree 10 points i) PreorderPrint Prints node values using a preorder traversal. 10 points j) Main Demonstrates all of the above methods.
Help is much appreciated!! Help is much appreciated!!
Explanation / Answer
#include<iostream>
using namespace std;
typedef struct node
{
int data;
node * llink=NULL;
node * rlink=NULL;
}node;
class bst
{
node * top;
int l=0,h=0,i=0;
int m[100];
public:
node * add(node *,int);
int preorder(node *);
int find(int,node *);
int leafcount(node *);
int height(node *);
node * balance(node *);
int isperfect(node *);
int numlevels(node *);
int ismirror(node *);
};
int bst::preorder(node * top)
{
if(top!=NULL)
{
m[i]=top->data;
i=i+1;
cout<<top->data;
preorder(top->llink);
preorder(top->rlink);
}
return 0;
}
node * bst::add(node * top,int data1)
{
int i,data2;
//cout<<"enter data";
//cin>>data1
top->data=data1;
cout<<"enter 1 to stop";
cin>>i;
if(i!=1)
{
cout<<"enter next data";
cin>>data2;
if(data2<=data1)
{
while(top->data>data2&&top->llink!=NULL)
{
top=top->llink;
}
if(top->data>data2)
{
top->rlink=new node;
add (top->rlink,data2);
}
else if(top->llink==NULL)
{
top->llink=new node;
add(top->llink,data2);
}
}
else
{
while(top->data<data2&&top->rlink!=NULL)
{
top=top->rlink;
}
if(top->data<data2)
{
top->llink=new node;
add (top->llink,data2);
}
else if(top->rlink==NULL)
{
top->rlink=new node;
add(top->rlink,data2);
}
//top->rlink=new node;
//create(top->rlink,data2);
}
}
return top;
}
int bst::find(int item,node * top)
{
node *n=top;
if(n->data==item)
{
return 1;
}
else if(n->data!=item&&n!=NULL)
{
find(item,n->llink);
find(item,n->rlink);
}
else
return 0;
}
int bst::leafcount(node * top)
{
if(top==NULL)
{
return l;
}
else
{
l=l+1;
leafcount(top->llink);
leafcount(top->rlink);
}
return l;
}
int bst::height(node * top)
{
if(top->rlink!=NULL&&top->llink!=NULL)
{
return 0;
}
else
{
h=h+1;
height(top->llink);
height(top->rlink);
}
return h;
}
int bst::numlevels(node *top)
{
int k;
k=height(top);
k=k-1;
return k;
}
int bst::isperfect(node * top)
{
if((top->llink!=NULL&&top->rlink!=NULL)||(top->llink==NULL&&top->rlink==NULL))
{
isperfect(top->llink);
isperfect(top->rlink);
return 1;
}
else
{
return 0;
}
}
int bst::ismirror(node * top)
{
if(top->llink==NULL)
{
return 1;
if(top->rlink==NULL)
{
return 2;
}
}
else if(top->rlink==NULL)
{
return 3;
}
else
{
if(ismirror(top->llink)==ismirror(top->rlink))
{
return 1;
}
else
{
return 0;
}
}
}
node * bst::balance(node * top)
{
int j=0;
node * top2;
preorder(top);
for(j=0;j<i;j++)
{
top2=add(top2,m[j]);
}
return top2;
}
int main()
{
bst a;
node * n;
int d,k,item;
cout<<"enter 1st data of bst";
cin>>d;
n=new node;
n=a.add(n,d);
a.preorder(n);
cout<<"enter data to find";
cin>>item;
if( a.find(item,n)==1)
{
cout<<"true"<<endl;
}
else
{
cout<<"false";
}
cout<<"leaf count is"<<a.leafcount(n);
cout<<"height is"<<a.height(n);
n=a.balance(n);
if(a.isperfect(n)==1)
{
cout<<"is perfect";
}
cout<<"no. of levels"<<a.numlevels(n);
if(a.ismirror(n)==1)
{
cout<<"is mirror";
}
}