(In C++ if possible.) 2. Create a binary tree structure that is populated by nod
ID: 3828176 • Letter: #
Question
(In C++ if possible.)
2. Create a binary tree structure that is populated by nodes that consist of a random integer and a frequency. The key is the integer value, the frequency is an integer that shows how many times that value has been generated. Allow the user to generate N random nodes, with N entered from the keyboard. Display the contents in a depth first manner to the screen. Then load those nodes into a pqueue based not on the value, but on the frequency. The nodes should be displayed as (value, frequency) pairs. Empty the queue and display them according to the priority criteria.
Explanation / Answer
// A C++ prgroam to contrcut all unique BSTs for keys from 1 to n
#include <iostream>
#include<vector>
using namespace std;
// node structure
struct node
{
int key;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = new node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to do preorder traversal of BST
void preorder(struct node *root)
{
if (root != NULL)
{
cout << root->key << " ";
preorder(root->left);
preorder(root->right);
}
}
// function for constructing trees
vector<struct node *> constructTrees(int start, int end)
{
vector<struct node *> list;
/* if start > end then subtree will be empty so returning NULL
in the list */
if (start > end)
{
list.push_back(NULL);
return list;
}
/* iterating through all values from start to end for constructing
left and right subtree recursively */
for (int i = start; i <= end; i++)
{
/* constructing left subtree */
vector<struct node *> leftSubtree = constructTrees(start, i - 1);
/* constructing right subtree */
vector<struct node *> rightSubtree = constructTrees(i + 1, end);
/* now looping through all left and right subtrees and connecting
them to ith root below */
for (int j = 0; j < leftSubtree.size(); j++)
{
struct node* left = leftSubtree[j];
for (int k = 0; k < rightSubtree.size(); k++)
{
struct node * right = rightSubtree[k];
struct node * node = newNode(i); // making value i as root
node->left = left; // connect left subtree
node->right = right; // connect right subtree
list.push_back(node); // add this tree to list
}
}
}
return list;
}
// Driver Program to test above functions
int main()
{
// Construct all possible BSTs
vector<struct node *> totalTreesFrom1toN = constructTrees(1, 3);
/* Printing preorder traversal of all constructed BSTs */
cout << "Preorder traversals of all constructed BSTs are ";
for (int i = 0; i < totalTreesFrom1toN.size(); i++)
{
preorder(totalTreesFrom1toN[i]);
cout << endl;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.