Write a C++ program to perform the following operations: It first prompts the us

Question

Write a C++ program to perform the following operations: It first prompts the user to input a sequence of integers to construct a binary search tree, in which each node has an additional field left Size. The definition of left Size is the same as given in the textbook. Print out the values of leftSize by level-order traversal, i.e. level by level and from left to right in each level. After the tree is constructed, allow a user to submit the following queries: The average of the SMALLEST k elements. If k exceeds the number of elements in the tree, return -1. The average of the LARGEST k elements. If k exceeds the number of elements in the tree, return-1. The median element of the entire BST. If the number of elements in the tree is even, return the average of the two median elements. Example 1: Average of SMALLEST 3 elements: 17 Average of LARGEST two elements: 42 Median element: 22

Explanation / Answer

# include <iostream>
# include <cstdlib>

struct node
{
int info;
struct node *left;
struct node *right;
}*root;

class BST
{
public:
void insert(int);
void inorder(node *);
    void smallest(int)
   void largest(int)
   void median(int)
void display(node *, int);
BST()
{
root = NULL;
}
};
int main()
{
int choice, num;
BST bst;
node *temp;

cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the number to be inserted : ";
   cin>>temp->info;
bst.insert(root, temp);
case 2:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 3:
cout<<"smallest of k elements:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<"largest of k elements:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 5:
cout<<"Median of the tree:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}

void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);  
   }
   else
   {
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}  
}
}
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}
cin<<"enter the value of k"<<end1
void smallest::smallest(node int)
{
int sum=0;
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
for(i=0;i<k;i++)
{
sum=sum + ptr[i];
}
cout<<sum/num<<END1
}
}
void largest::largest(node int)
{
int sum1=0;
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
for(i=num;i>=k;i++)
{
sum1=sum1 + ptr[i];
}
cout<<sum1/num<<END1
}
}
void Median::Median(node int)
{
int sum2=0;
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
for(i=0;i<num;i++)
{
sum2=sum2 + ptr[i];
}
cout<<sum2/num<<END1
}
}
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
   }
cout<<ptr->info;
display(ptr->left, level+1);
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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