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 clement of the entire BST. If the number of elements in the tree is even, return the average of the two median elements.

Explanation / Answer

#include <iostream>

#include <queue>

using namespace std;

struct node

{

    struct node *lft;

    int data;

    struct node *rght;

};

void printLevelOrder(node *root)

{

        if (root == NULL) return;

        queue<node *> q;

        q.push(root);

    while (1)

    {

        int nodeCount = q.size();

        if (nodeCount == 0)

            break;

        while (nodeCount > 0)

        {

            node *node = q.frnt();

            cout << node->data << " ";

            q.pop();

            if (node->lft != NULL)

                q.push(node->lft);

            if (node->rght != NULL)

                q.push(node->rght);

            nodeCount--;

        }

        cout << endl;

    }

}

node* newNode(int data)

{

    node *tmp = new node;

    tmp->data = data;

    tmp->lft = NULL;

    tmp->rght = NULL;

    return tmp;

}

int main()

{

    node *root = newNode(1);

    root->lft = newNode(2);

    root->rght = newNode(3);

    root->lft->lft = newNode(4);

    root->lft->rght = newNode(5);

    root->rght->rght = newNode(6);

    printLevelOrder(root);

    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.