int ReturnSet public void Generateset (const Node node int array, int &position;
ID: 3804114 • Letter: I
Question
int ReturnSet public void Generateset (const Node node int array, int &position; private The Returnset will return a sorted array of the items in the tree. This method will create an array using dynamic memory allocation that is the size of the number of nodes in the tree. This array will be populated by the Generateset method. ReturnSet calls Generateset and passes it the root of the tree, the pointer to the created array, and the start position in the array (i.ee index zero). Below is an example function call to Generateset made by ReturnSet int start position 30; Generateset(root, array, start position Generateset will populate the array by performing the recursive in-order traversal of the tree and initializing the array element at position to the value of the node's data. The result will be an array of the values in the tree stored in ascending order. It is left up to you to determine how this is done and when to update the position parameter during this traversal. It should be noted that you must have a clear understanding about how arrays are handled when passed as arguments to functions, how reference variables work when modified by a function, and recursion.Explanation / Answer
The idea is to implement all the methods correctly.
#include <bits/stdc++.h>
using namespace std;
class Bst {
private:
class Node {
public:
int key;
Node *left;
Node *right;
Node(int key) {
this->key = key;
left = NULL;
right = NULL;
}
};
Node *root;
int size;
public:
Bst() {
root = NULL;
size = 0;
}
void insert(int key);
int* ReturnSet();
void GenerateSet(const Node *node, int *array, int &position);
};
int* Bst::ReturnSet() {
int *array = new int[size];
int idx = 0;
GenerateSet(root, array, idx);
return array;
}
void Bst::GenerateSet(const Node *node, int *array, int &position) {
if (!node)
return;
GenerateSet(node->left, array, position);
array[position] = node->key;
++position;
GenerateSet(node->right, array, position);
}
void Bst::insert(int key) {
if (root == NULL) {
root = new Node(key);
++size;
return;
}
Node *temp = root;
while (true) {
if (temp->key > key) {
if (!temp->left) {
temp->left = new Node(key);
break;
} else {
temp = temp->left;
}
} else {
if (!temp->right) {
temp->right = new Node(key);
break;
} else {
temp = temp->right;
}
}
}
++size;
}
int main() {
Bst b;
b.insert(7);
b.insert(3);
b.insert(11);
b.insert(5);
b.insert(1);
b.insert(9);
int *arr = b.ReturnSet();
for (int i = 0; i < 6; ++i) {
cout << arr[i] << ", ";
}
return 0;
}
The output of the above code is:
1, 3, 5, 7, 9, 11,
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.