Question

C++

Generate 100 random numbers of the values 1-20 in an input.txt. Now create a binary search tree using the numbers of the sequence. The tree set should not have any nodes with same values and all repeated numbers of the random sequence must be stored in the node as a counter variable. For example, if there are five 20s’ in the random sequence then the tree node having data 20 has counter variable equal to 5.

Sort the sequence of numbers including repeat numbers using Binary Tree traversal.

Answer 1

PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU

#include <iostream>
#include <iomanip>

using namespace std;

struct Node
{
        int val;
        int count;
        Node *left;
        Node *right;
};
int index = 0; // to store elements in sorted array


Node *make_new_node(int val)
{
        Node *child = new Node();
        child->val = val;
        child->count = 1;
        child->left = NULL;
        child->right = NULL;
        return child;
}

//Construct the Binary search tree using the Array generated and return the root of tree
Node *makeTree(int arr[])
{
        Node *root = NULL;
        for (int i = 0; i < 100; i++)
        {
                if (root == NULL)
                {
                        Node *node = make_new_node(arr[i]);
                        root = node;
                }
                else
                {
                        Node *temp = root;
                        while (true)
                        {
                                if (temp != NULL)
                                {
                                        if (arr[i] == temp->val)
                                        {
                                                (temp->count)++;
                                                break;
                                        }
                                        else if (arr[i] < temp->val)
                                        {
                                                if (temp->left == NULL)
                                                {
                                                        Node *newNode = make_new_node(arr[i]);
                                                        temp->left = newNode;
                                                        break;
                                                }
                                                else
                                                {
                                                        temp = temp->left;
                                                }
                                        }
                                        else if (arr[i] > temp->val)
                                        {
                                                if (temp->right == NULL)
                                                {
                                                        Node *newNode = make_new_node(arr[i]);
                                                        temp->right = newNode;
                                                        break;
                                                }
                                                else
                                                {
                                                        temp = temp->right;
                                                }
                                        }
                                }
                        }
                }
        }
        return root;
}


void SortUsingBinaryTraversal(Node *root, int *arr)
{
        if (root->left != NULL)
                SortUsingBinaryTraversal(root->left, arr);

        for (int i = 0; i < root->count; i++)
        {
                //insert all occurences of value on current node
                arr[index++] = root->val;
        }
        if (root->right != NULL)
                SortUsingBinaryTraversal(root->right, arr);
}

int main()
{
        int arr[100];
        //generate the array of random 100 integers each having value from 1 to 20
        srand(time(0));
        for (int i = 0; i < 100; i++)
        {
                int num = (rand() % 20) + 1;
                arr[i] = num;
        }

        //Print the randomly generated array in 10 by 10 matrix form
        cout << "Randomly Generated array is:" << endl
             << endl;
        for (int i = 0; i < 10; i++)
        {
                for (int j = 0; j < 10; j++)
                {
                        cout << left << setw(5) << arr[i * 10 + j];
                }
                cout << endl;
        }
        cout << endl;

        //Construct Binary Search tree on the generated array
        Node *root = makeTree(arr);

        //Sort the array using Binary Tree Traversal
        int sortedArray[100];
        SortUsingBinaryTraversal(root, sortedArray);

        //Print Sorted array in 10 by 10 matrix form
        cout << "Sorted Array is:" << endl
             << endl;
        for (int i = 0; i < 10; i++)
        {
                for (int j = 0; j < 10; j++)
                {
                        cout << left << setw(5) << sortedArray[i * 10 + j];
                }
                cout << endl;
        }
}