Write a C program that implements a binary search tree BST t

Write a C++ program that implements a binary search tree (BST) to manage a number of integer items with different priorities. In order to do so. you will need to maintain a queue as an item in the tree. Each queue item is an integer. All items in a given queue will have the same priority. As a new item with a user-specified priority comes in, it should be enqueued in the queue with items of that priority. A new queue may need to created in case a queue with that priority does not exist. Use dynamic memory to manage nodes in the queue and BST. Implement the following: Constructor. Destructor. Overloaded copy constructor. Overloaded assignment operator. Overloaded \"==\" operator to check if two trees are equal. A tree t1 is equal to t2 if for every queue in t1, a corresponding queue with the same priority exists in t2 with the same set of elements (the order of the elements in the queue docs not matter). Overloaded \"

Solution

program using namespace std;
#define width_unit 5
class BStree
{
private:
class Node
{
public:
int data;
Node *left, *right;
Node(int d=0)
:data(d), left(NULL), right(NULL) {}
};
Node *root;
Node * trav(int, Node * &);
void chop(Node * N);
void copy(Node * N);
void print(ostream &, Node *, int) const;
void print(Node *, int) const;
public:
BStree(void);
~BStree(void);
bool find(int);
void insert(int);
void remove(int);
bool empty(void) const;
Tree(const BStree &);
const BStree & operator=(const BStree &);
friend ostream & operator<<(ostream &, const BStree &);
};
BStree::BStree(void)
{
root=NULL;
}
bool Tree::empty(void) const
{
return !root;
}
BStree::Node * BStree::trav(int foo, Node * & par)
{
Node * curr=root;
par=NULL;
while(curr && curr->data != foo)
{
par=curr;
if(foo < curr->data)
curr=curr->left;
else
curr=curr->right;
}
return curr;
}
bool BStree::find(int foo)
{
Node * par=NULL;
Node * curr=trav(foo, par);
return curr;
}
void BStree::insert(int foo)
{
Node * par=NULL;
Node * curr=trav(foo,par);
if(!curr)
{
curr= new Node(foo);
if(!par)
root=curr;
else if(foo < par->data)
par->left=curr;
else
par->right=curr;
}
}
void BStree::remove(const int foo)
{
Node * par=NULL;
Node * curr=trav(foo,par);
if(curr)
{
if(curr->left && curr->right)
{
Node * tmp=curr;
par=curr;
curr=curr->left;
while(curr->right)
{
par=curr;
curr=curr->right;
}
tmp->data=curr->data;
}
Node *tmp=(curr->left ? curr->left : curr->right);
if(!par)
root=tmp;
else if(par->data < curr->data)
par->right=tmp;
else
par->left=tmp;
delete curr;
}
}
void BStree::chop(Node *N)
{
if(N)
{
chop(N->left);
chop(N->right);
delete N;
}
}
BStree::~BStree(void)
{
chop(root);
}
BStree::BStree(const BStree & T)
{
root=NULL;
copy(T.root);
}
void BStree::copy(Node * N)
{
if(N)
{
insert(N->data);
copy(N->left);
copy(N->right);
}
}
const BStree & BStree::operator=(const BStree & T)
{
if(this != &T)
{
chop(root);
root=NULL;
copy(T.root);
}
return *this;
}
void BStree::print(ostream & ost, Node * curr, int level) const
{
if(curr)
{
print(ost,curr->right,level+1);
ost<<setw(level*width_unit)<<curr->data<<endl;
print(ost,curr->left,level+1);
}
}
void BStree::print(Node * curr, int level) const
{
if(curr)
{
print(curr->right,level+1);
cout<<setw(level*width_unit)<<curr->data<<endl;
print(curr->left,level+1);
}
}
ostream & operator<<(ostream &ost, const BStree &t)
{
t.print(ost, t.root, 1);
return ost;
}
int main()
{
BStree mytree;
mytree.insert(5);
mytree.insert(3);
mytree.insert(2);
mytree.insert(7);
mytree.insert(0);
mytree.insert(2);
cout<<mytree<<endl<<endl;
mytree.remove(0);
cout<<mytree<<endl<<endl;
mytree.remove(5);
cout<<mytree<<endl<<endl;
mytree.insert(9);
mytree.insert(10);
mytree.insert(4);
cout<<mytree<<endl<<endl;
mytree.remove(9);
cout<<mytree<<endl<<endl;
BStree mytree2=mytree;
cout<<mytree2<<endl<<endl;
BStree mytree3;
mytree3=mytree2;
cout<<mytree3<<endl<<endl;
return 0;
}