Question

You are going to implement Treesort algorithm in C++ to sort string data. Here are the steps to complete the homework 1) Use the following class definition for binary search tree nodes. Its constructor is incomplete you should first complete the constructor. class TreeNode t public: string data; / this is the string stored in the node TreeNode left: TreeNode right; TreeNode (string element, TreeNode 1t, TreeNode rt //your code here 2) Write a function that will insert a string into a binary search tree. Use the following function header void insertl int x, TreeNode t 3) Write the function treesort using the following header: TreeNode * treesort (string arr[], int n The function treesort should update the array so that the array elements are in increasing order. Your function should implement the algorithm given above. Any other sorting algorithm will not get any credits. Note that the function return type is a pointer to a TreeNode. The function should return a pointer to the root of the binary search tree that is created in the treesort function. I will use that pointer to test the correctness of your function. 4) Write a main function to test your functions. The main function should first read the size N of the array. Then it should prompt the user to enter a data file name. N strings should be read from the file into the array. It should then call the treeSort) to sort the read data. The sorted data should be printed as a result. Data file should include one data element per line. It may include any information like names of people, abbreviations, barcodes ete. Here is a sample run of the program:

Answer 1

// Example program
#include <iostream>
#include <string>
using namespace std;

class TreeNode {
public:
string data;
TreeNode *left;
TreeNode *right;
TreeNode(string element, TreeNode *lt, TreeNode *rt) {
data=element;
left=lt;
right=rt;
}
void insert(string x, TreeNode* &root) {
if(root==NULL) {
root = new TreeNode(x, NULL, NULL);
return;
}   
else if(x< root->data)
insert(x, root->left);
else
insert(x, root->right);
}
  
void printOrder(TreeNode *node) {
if(node==NULL)
return;
else {
printOrder(node->left);
cout<<node->data<<"\n";
printOrder(node->right);
}
}
  
TreeNode * treeSort(string *arr, int& n) {
TreeNode *root=NULL;
for(int i=0; i<n; i++) {
insert(arr[i], root);   
}
printOrder(root);
}
};

int main() {
TreeNode bst("", NULL, NULL);
int N;
cout<<"Enter number of elements to insert: ";
cin>>N;
string* list=new string[N];
for(int i=0; i<N; i++) {
cin>>list[i];
  
}
bst.treeSort(list, N);
// system("pause");
return 0;
}

null