
C++ Programming Homework Help on Generic Binary Search Tree Project
- 26th May, 2022
- 15:15 PM
#include #include #include #include #include #include #include #include using namespace std; int type = -1; // 0 for int, 1 for double, 2 for string vector types; // strip the spaces from both ends of the string string strip(string& s){ s = regex_replace(s, regex("^ +"), ""); s = regex_replace(s, regex(" +$"), ""); return s; } // split the line of string at the delimiter positions vector split(string str, string delimiter = ","){ vector res; size_t pos = 0; string token; while((pos = str.find(delimiter)) != string::npos){ token = str.substr(0, pos); res.push_back(strip(token)); str.erase(0, pos + delimiter.length()); } res.push_back(strip(str)); return res; } // read text from the standard input from the user vector> read(string filename){ vector> res; string str; ifstream in(filename); streambuf *cinbuf = cin.rdbuf(); cin.rdbuf(in.rdbuf()); while(getline(cin, str)){ if(type == -1){ if(isdigit(str[0])){ if(str.find(".") != string::npos) type = 1; else type = 0; } else type = 2; } res.push_back(split(str)); types.push_back(type); type = -1; } return res; } template class TreeNode{ public: T val; TreeNode *left; TreeNode *right; TreeNode(T x) : val(x), left(NULL), right(NULL) {} }; template class BST{ TreeNode* root = NULL; stack*> sta; TreeNode* insert(TreeNode* root, T key){ TreeNode* newNode = new TreeNode(key); TreeNode* x = root; TreeNode* y = NULL; while(x){ y = x; if(key < x->val) x = x->left; else x = x->right; } if(!y) y = newNode; else if(key < y->val) y->left = newNode; else y->right = newNode; return y; } public: BST(const vector& tokens){ for(const auto& token : tokens){ if(!root){ root = insert(root, token); } else{ insert(root, token); } } } void inOrder(){ TreeNode* curr = root; while(curr || !sta.empty()){ while(curr){ sta.push(curr); curr = curr->left; } curr = sta.top(); sta.pop(); cout << curr->val << " "; curr = curr->right; } cout << endl << endl; } void postOrder(TreeNode* node){ if(!node) return; postOrder(node->left); postOrder(node->right); delete node; } void freeTree(){ postOrder(root); } }; int main(int argc, char *argv[]){ vector> tokens = read(argv[1]); //for(auto token : tokens) cout << token << endl; for(int i=0; i cout << "LINE - " << i << ":" << endl; type = types[i]; if(type == 0){ vector res; for(auto token : tokens[i]){ try{ res.push_back(stoi(token)); } catch(exception& e){ cout << "cannot convert " << token << " to int." << endl; } } BST* bst = new BST(res); bst->inOrder(); bst->freeTree(); } else if(type == 1){ vector res; for(auto token : tokens[i]){ try{ res.push_back(stod(token)); } catch(exception& e){ cout << "cannot convert " << token << " to double." << endl; } } BST* bst = new BST(res); bst->inOrder(); bst->freeTree(); } else{ BST* bst = new BST(tokens[i]); bst->inOrder(); bst->freeTree(); } } return 0; }