You are to use a binary search tree to implement a priority queue. Write a C++ p

Question

You are to use a binary search tree to implement a priority queue. Write a C++ program that do the following: It first prompts the user for entering a sequence of data elements of type int and constructs a binary search tree by inserting these elements one by one. This binary search tree represents a max priority queue. The user then inserts or deletes from the max priority queue from a menu. Note that, to demonstrate that the binary search tree is correctly restructured after each insertion or deletion, print out the tree using level-order traversal. In addition, you have to implement a function called computsize which returns the total number of elements in the left subtree of an element given by the user.

Explanation / Answer

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

struct node
{
   int priority;
   int info;
   struct node *link;
};

class Priority_Queue
{
private:
node *front;
public:
Priority_Queue()
{
front = NULL;
}
  
void insert(int item, int priority)
{
node *tmp, *q;
tmp = new node;
tmp->info = item;
tmp->priority = priority;
if (front == NULL || priority < front->priority)
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while (q->link != NULL && q->link->priority <= priority)
q=q->link;
tmp->link = q->link;
q->link = tmp;
}
}

void del()
{
node *tmp;
if(front == NULL)
cout<<"Queue Underflow ";
else
{
tmp = front;
cout<<"Deleted item is: "<<tmp->info<<endl;
front = front->link;
free(tmp);
}
}
  
void display()
{
node *ptr;
ptr = front;
if (front == NULL)
cout<<"Queue is empty ";
else
{   cout<<"Queue is : ";
cout<<"Priority Item ";
while(ptr != NULL)
{
cout<<ptr->priority<<" "<<ptr->info<<endl;
ptr = ptr->link;
}
}
}
};

int main()
{
int choice, item, priority;
Priority_Queue pq;
do
{
cout<<"1.Insert ";
cout<<"2.Delete ";
cout<<"3.Display ";
cout<<"4.Quit ";
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>item;
cout<<"Enter its priority : ";
cin>>priority;
pq.insert(item, priority);
break;
case 2:
pq.del();
break;
case 3:
pq.display();
break;
case 4:
break;
default :
cout<<"Wrong choice ";
}
}
while(choice != 4);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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