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 leftSize. The definition of leftSize 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 <vector>
#include <queue>
using namespace std;

struct node{
   int value;
   node *leftChild,*rightChild;
   int leftSize=0;
    node(int v,node *lc, node *rc){
        value=v;
        leftChild=lc;
      rightChild=rc;
    }
};

class binaryTree{
    public:
node *root=NULL;

    void insert(int n){
    if(root==NULL){
        root=new node(n,NULL,NULL);
    }
    else{
    node *currentNode=root;
   int t=1;
   while(1){
       if(n<=currentNode->value && currentNode->leftChild!=NULL){
           currentNode->leftSize++;
           currentNode=currentNode->leftChild;
       }
       else if(currentNode->rightChild!=NULL){
           currentNode=currentNode->rightChild;
       }
       else{
           break;
       }
   }
   node *tempNode=new node(n,NULL,NULL);
   if(n<=currentNode->value){
       currentNode->leftChild=tempNode;
       currentNode->leftSize++;
   }
   else{
       currentNode->rightChild=tempNode;
   }
      }
      }

      void levelOrderTraversal(){
          deque<node*> bfs;
          bfs.push_back(root);
          while(!bfs.empty()){
              node *tempNode=bfs.front();
              if(tempNode->leftChild!=NULL){
                  bfs.push_back(tempNode->leftChild);
              }
              if(tempNode->rightChild!=NULL){
                  bfs.push_back(tempNode->rightChild);
              }
              bfs.pop_front();
              cout<<tempNode->leftSize<<" ";
          }
      }
};

int main(){
binaryTree tree;
tree.insert(20);
tree.insert(17);
tree.insert(14);
tree.insert(36);
tree.insert(22);
tree.insert(28);
tree.insert(48);
// cout<<tree.root->rightChild->rightChild->value;
tree.levelOrderTraversal();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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