code. compile. run. debug. share.
#include "TBST.h"
#include "helpers.h"
void insertHandler(TBST* tree, std::vector<std::string> args)
{
const int ID_INDEX = 1;
const int NAME_INDEX = 2;
const int NUM_OF_ARGUMENTS = 3;
if (tree == NULL)
{
std::cerr << "The tree is not exist, a tree object must be initialized" << std::endl;
return;
}
else if (args.size() < NUM_OF_ARGUMENTS)
{
std::cerr << "This command requires at least " << NUM_OF_ARGUMENTS << " arguments (including the command itself)" << std::endl;
return;
}
try
{
int id = std::stoi(args[ID_INDEX]);
std::string name = join(args, NAME_INDEX);
tree->insert(id, name);
}
catch (std::invalid_argument& exception)
{
std::cerr << "A student id must contain only integer numbers" << std::endl;
}
catch (std::out_of_range& exception)
{
std::cerr << "Student id number is too big. Please try again with smaller number" << std::endl;
}
}
void removeHandler(TBST* tree, std::vector<std::string> args)
{
const int ID_INDEX = 1;
const int NUM_OF_ARGUMENTS = 2;
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
else if (args.size() != NUM_OF_ARGUMENTS)
{
std::cerr << "This command requires " << NUM_OF_ARGUMENTS << " arguments (including the command itself)" << std::endl;
return;
}
try
{
int id = std::stoi(args[ID_INDEX]);
tree->remove(id);
}
catch (std::invalid_argument& exception)
{
std::cerr << "A student id must contain only integer numbers" << std::endl;
}
catch (std::out_of_range& exception)
{
std::cerr << "Student id number is too big. Please try again with smaller number" << std::endl;
}
}
void searchHandler(TBST* tree, std::vector<std::string> args)
{
const int ID_INDEX = 1;
const int NUM_OF_ARGUMENTS = 2;
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
else if (args.size() != NUM_OF_ARGUMENTS)
{
std::cerr << "This command requires " << NUM_OF_ARGUMENTS << " arguments (including the command itself)" << std::endl;
return;
}
try
{
int id = std::stoi(args[ID_INDEX]);
TNode* node = tree->search(id);
if (node != NULL)
{
std::cout << "The name of the student with ID " << id << ", is: " << *(node->student_name) << std::endl;
}
}
catch (std::invalid_argument& exception)
{
std::cerr << "A student id must contain only integer numbers" << std::endl;
}
catch (std::out_of_range& exception)
{
std::cerr << "Student id number is too big. Please try again with smaller number" << std::endl;
}
}
void successorHandler(TBST* tree, std::vector<std::string> args)
{
const int ID_INDEX = 1;
const int NUM_OF_ARGUMENTS = 2;
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
else if (args.size() != NUM_OF_ARGUMENTS)
{
std::cerr << "This command requires " << NUM_OF_ARGUMENTS << " arguments (including the command itself)" << std::endl;
return;
}
try
{
int id = std::stoi(args[ID_INDEX]);
TNode* node = tree->tree_successor(tree->search(id));
if (node != NULL)
{
std::cout << "The successor of student id " << id << " is student id " << node->student_id << std::endl;
}
else
throw std::runtime_error("No successor");
}
catch (std::invalid_argument& exception)
{
std::cerr << "A student id must contain only integer numbers" << std::endl;
}
catch (std::out_of_range& exception)
{
std::cerr << "Student id number is too big. Please try again with smaller number" << std::endl;
}
catch (...)
{
std::cerr << "There is no successor for the student id you requested" << std::endl;
}
}
void predecessorHandler(TBST* tree, std::vector<std::string> args)
{
const int ID_INDEX = 1;
const int NUM_OF_ARGUMENTS = 2;
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
else if (args.size() != NUM_OF_ARGUMENTS)
{
std::cerr << "This command requires " << NUM_OF_ARGUMENTS << " arguments (including the command itself)" << std::endl;
return;
}
try
{
int id = std::stoi(args[ID_INDEX]);
TNode* node = tree->tree_predecessor(tree->search(id));
if (node != NULL)
{
std::cout << "The predecessor of student id " << id << " is student id " << node->student_id << std::endl;
}
else
throw std::runtime_error("No predecessor");
}
catch (std::invalid_argument& exception)
{
std::cerr << "A student id must contain only integer numbers" << std::endl;
}
catch (std::out_of_range& exception)
{
std::cerr << "Student id number is too big. Please try again with smaller number" << std::endl;
}
catch (...)
{
std::cerr << "There is no predecessor for the student id you requested" << std::endl;
}
}
void minimumHandler(TBST* tree)
{
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
int min = TBST::tree_minimum(tree->root)->student_id;
std::cout << "The minimum student id in the BST is: " << min << std::endl;
}
void maximumHandler(TBST* tree)
{
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
int max = TBST::tree_maximum(tree->root)->student_id;
std::cout << "The maximum student id in the BST is: " << max << std::endl;
}
void pre_orderHandler(TBST* tree)
{
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
TBST::preOrderTraversal(tree->root);
}
void in_orderHandler(TBST* tree)
{
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
TBST::inOrderTraversal(tree->root);
}
void post_orderHandler(TBST* tree)
{
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
TBST::postOrderTraversal(tree->root);
}
void medianHandler(TBST* tree)
{
if (tree == NULL || tree->root == NULL)
{
std::cerr << "The tree is empty, please insert students into the BST" << std::endl;
return;
}
int median = tree->getMedian()->student_id;
std::cout << "The median student id in the BST is: " << median << std::endl;
}
int main()
{
TBST* tree = new TBST();
command_list* cmd = new command_list;
printHelp();
std::cout << "> ";
for (std::string line; std::getline(std::cin, line);)
{
std::cout << std::endl;
if (line.length() == 0)
{
std::cout << "> ";
continue;
}
std::vector<std::string> args = split(line);
toUpperCase(args[0]);
if (args[0].compare(cmd->insert) == 0)
insertHandler(tree, args);
else if (args[0].compare(cmd->remove) == 0)
removeHandler(tree, args);
else if (args[0].compare(cmd->search) == 0)
searchHandler(tree, args);
else if (args[0].compare(cmd->successor) == 0)
successorHandler(tree, args);
else if (args[0].compare(cmd->predecessor) == 0)
predecessorHandler(tree, args);
else if (args[0].compare(cmd->minimum) == 0)
minimumHandler(tree);
else if (args[0].compare(cmd->maximum) == 0)
maximumHandler(tree);
else if (args[0].compare(cmd->pretraversal) == 0)
pre_orderHandler(tree);
else if (args[0].compare(cmd->intraversal) == 0)
in_orderHandler(tree);
else if (args[0].compare(cmd->posttraversal) == 0)
post_orderHandler(tree);
else if (args[0].compare(cmd->median) == 0)
medianHandler(tree);
else
printHelp();
std::cout << "> ";
}
delete tree;
delete cmd;
return 0;
}
#ifndef HELPERS
#define HELPERS
#ifndef IOSTREAM
#define IOSTREAM
#include <iostream>
#endif
#ifndef SSTREAM
#define SSTREAM
#include <sstream>
#endif
#ifndef VECTOR
#define VECTOR
#include <vector>
#endif
#ifndef ITERATOR
#define ITERATOR
#include <iterator>
#endif
#ifndef ALGORITHM
#define ALGORITHM
#include <algorithm>
#endif
#pragma once
typedef struct
{
std::string search = "SEARCH";
std::string insert = "INSERT";
std::string remove = "REMOVE";
std::string median = "MEDIAN";
std::string intraversal = "INORDERTRAVERSAL";
std::string pretraversal = "PREORDERTRAVERSAL";
std::string posttraversal = "POSTORDERTRAVERSAL";
std::string predecessor = "PREDECESSOR";
std::string successor = "SUCCESSOR";
std::string minimum = "MINIMUM";
std::string maximum = "MAXIMUM";
} cmd;
/*
Description: removes all whitespaces from the beginning of the string
*/
std::string trim_left(const std::string& str);
/*
Description: removes all whitespaces from the end of the string
*/
std::string trim_right(const std::string& str);
/*
Description: removes all whitespaces from the from the beginning of the string and the end of the string
*/
std::string trim(const std::string& str);
/*
Description: split a string by whitespace and return an array of the substrings
*/
std::vector<std::string> split(std::string const &input);
/*
Description: join an array of strings from a given index, to a single string with backspace between each joined string
*/
std::string join(std::vector<std::string>, int begin);
/*
Description: transform all lowercase letters in the string to uppercase letters
*/
void toUpperCase(std::string& str);
/*
Description: print the usage instructions of the program
*/
void printHelp(void);
#endif
#include "helpers.h"
void printHelp()
{
command_list* cmd = new command_list;
std::cout << "Usage:" << std::endl;
std::cout << "Insert a new student to the BST:\t" << cmd->insert << " [STUDENT_ID] [STUDENT_NAME]" << std::endl;
std::cout << "Remove a student from the BST:\t" << cmd->remove << " [STUDENT_ID]" << std::endl;
std::cout << "Search a student in the BST:\t" << cmd->search << " [STUDENT_ID]" << std::endl;
std::cout << "Get the successor of a student in the BST:\t" << cmd->successor << " [STUDENT_ID]" << std::endl;
std::cout << "Get the predecessor of a student in the BST:\t" << cmd->predecessor << " [STUDENT_ID]" << std::endl;
std::cout << "Get the minimum student id in the BST:\t" << cmd->minimum << std::endl;
std::cout << "Get the maximum student id in the BST:\t" << cmd->maximum << std::endl;
std::cout << "Print the BST with pre-order-traversal:\t" << cmd->pretraversal << std::endl;
std::cout << "Print the BST with in-order-traversal:\t" << cmd->intraversal << std::endl;
std::cout << "Print the BST with post-order-traversal:\t" << cmd->posttraversal << std::endl;
std::cout << "Get the median student id in the BST:\t" << cmd->median << std::endl;
std::cout << std::endl;
delete cmd;
}
void toUpperCase(std::string& str)
{
std::transform(str.begin(), str.end(), str.begin(), ::toupper);
}
std::string trim_left(const std::string& str)
{
const std::string pattern = " \f\n\r\t\v";
return (str.length() > 0) ? str.substr(str.find_first_not_of(pattern)) : str;
}
std::string trim_right(const std::string& str)
{
const std::string pattern = " \f\n\r\t\v";
return (str.length() > 0) ? str.substr(0, str.find_last_not_of(pattern) + 1) : str;
}
std::string trim(const std::string& str) //using recursion
{
return trim_left(trim_right(str));
}
std::string join(const std::vector<std::string> args, int begin)
{
std::string output;
for (unsigned int i = begin; i < args.size(); i++)
{
output += (i < args.size() - 1) ? args[i] + " " : args[i];
}
return output;
}
std::vector<std::string> split(std::string const &input)
{
std::istringstream buffer(input);
std::vector<std::string> ret((std::istream_iterator<std::string>(buffer)),
std::istream_iterator<std::string>());
return ret;
}
#ifndef STRING
#define STRING
#include <string>
#endif
#ifndef MATH
#define MATH
#include <math.h>
#endif
#ifndef IOSTREAM
#define IOSTREAM
#include <iostream>
#endif
#ifndef TBST
#define TBST
#pragma once /* pre compiler instruction for future usage of the threaded node struct */
typedef struct TNode /* the given properties of the binary search tree in addition to the name and id of the students */
{
struct TNode* parent = NULL;
struct TNode* left = NULL;
struct TNode* right = NULL;
std::string* student_name;
int id;
} TNode;
class TBST /*an interface to implement all the neccesary commands from the handout */
{
public:
TNode* root;
TNode* getMedian();
TNode* search(int);
void insert(int, std::string);
void remove(int);
static void inOrderTraversal(TNode*);
static void preOrderTraversal(TNode*);
static void postOrderTraversal(TNode*);
static TNode* tree_minimum(TNode*);
static TNode* tree_maximum(TNode*);
static TNode* T_predecessor(TNode*);
static TNode* T_successor(TNode*);
static TNode* T_min(TNode*);
static TNode* T_max(TNode*);
TBST();
TNode *root;
~TBST();
protected:
int size;
TNode* median;
private:
static void printNode(TNode*); /* printing students' name and id */
static bool rightChildNotThread(TNode*); /* returns true if exists a right child who is not a thread */
static bool leftChildNotThread(TNode*); /* returns true if exists a left child who is not a thread */
static bool childrenNotThread(TNode*); /* returns true if neither of the children of the node is not a thread */
void removeSubTree(TNode*); /* removing a subtree from the node */
void updateMedian(); /* giving an anchor after altering the median */
int smallerThanMedian; /* number of students whose id is smaller than the median id */
int largerThanMedian; /* number of students whose id is larger than the median id */
};
#endif
#include "TBST.h"
TBST::TBST() //constructor
{
}
void TBST::insert(int id, std::string name)
{
if (name.empty()) {cout<<"no name was given"; return;}
TNode* x = this->root;
TNode* y = NULL;
while (x != NULL && x->parent == y)
{
y = x;
if (id < x->student_id)
{
x = x->left;
}
else if (id > x->student_id)
{
x = x->right;
}
else
return;
}
TNode* node = new TNode; //Initialization
node->student_id = id;
node->student_name = new std::string(name);
if (y == NULL)
{
this->root = node;
}
else if (id < y->student_id)
{
node->left = y->left;
y->left = node;
node->parent = y;
node->right = y;
}
else
{
node->right = y->right;
y->right = node;
node->parent = y;
node->left = y;
}
this->size += 1;
if (this->median != NULL)
{
if (id > this->median->student_id)
this->largerThanMedian += 1;
else if (id < this->median->student_id)
this->smallerThanMedian += 1;
}
updateMedian();
}
void TBST::remove(int id)
{
TNode* node = search(id);
if (node == NULL)
return;
TNode* succ = tree_successor(node);
TNode* pred = tree_predecessor(node);
if (childrenNotThread(node))
{
if (succ->parent != node && rightChildNotThread(succ))
{
succ->right->parent = succ->parent;
succ->parent->left = succ->right;
}
succ->left = node->left;
succ->left->parent = succ;
if (succ != node->right)
{
succ->right = node->right;
node->right->parent = succ;
}
succ->parent = node->parent;
if (succ->parent == NULL)
this->root = succ;
else if (succ->parent->left == node)
succ->parent->left = succ;
else
succ->right->parent = succ;
pred->right = succ;
}
else if (rightChildNotThread(node))
{
node->right->parent = node->parent;
if (node->parent != NULL && node->parent->left == node)
node->parent->left = node->right;
else if (node->parent != NULL && node->parent->right == node)
node->parent->right = node->right;
else
this->root = node->right;
succ->left = pred;
}
else if (leftChildNotThread(node))
{
node->left->parent = node->parent;
if (node->parent != NULL && node->parent->left == node)
node->parent->left = node->left;
else if (node->parent != NULL && node->parent->right == node)
node->parent->right = node->left;
else
this->root = node->left;
pred->right = succ;
}
else
{
if (node->parent != NULL && node->parent->left == node)
node->parent->left = pred;
else if (node->parent != NULL && node->parent->right == node)
node->parent->right = succ;
else
this->root = NULL;
}
if (node == this->root)
{
if (succ != NULL)
this->root = succ;
else
this->root = pred;
}
this->size -= 1;
if (node == this->median)
{
if (succ != NULL)
{
this->median = succ;
this->largerThanMedian -= (largerThanMedian > 0) ? 1 : 0;
}
else
{
this->median = pred;
this->smallerThanMedian -= (smallerThanMedian > 0) ? 1 : 0;
}
}
else
{
if (id > this->median->student_id)
this->largerThanMedian -= (largerThanMedian > 0) ? 1 : 0;
else if (id < this->median->student_id)
this->smallerThanMedian -= (smallerThanMedian > 0) ? 1 : 0;
}
updateMedian();
if (node->student_name != NULL)
{
delete node->student_name;
node->student_name = NULL;
}
delete node;
}
TNode* TBST::search(int id)
{
TNode* x = this->root;
while (x != NULL && id != x->student_id)
{
if (id < x->student_id)
{
if (leftChildNotThread(x))
x = x->left;
else
return NULL;
}
else if (id > x->student_id)
{
if (rightChildNotThread(x))
x = x->right;
else
return NULL;
}
}
return x;
}
TNode* TBST::tree_predecessor(TNode* x)
{
if (x == NULL)
return NULL;
if (x->left != NULL && x->left->parent == x)
{
return tree_maximum(x->left);
}
TNode* y = x->parent;
while (y != NULL && x == y->left)
{
x = y;
y = y->parent;
}
return y;
}
TNode* TBST::tree_successor(TNode* x)
{
if (x == NULL)
return NULL;
if (x->right != NULL && x->right->parent == x)
{
return tree_minimum(x->right);
}
TNode* y = x->parent;
while (y != NULL && x == y->right)
{
x = y;
y = y->parent;
}
return y;
}
TNode* TBST::tree_minimum(TNode* x) //using recursion to find min
{
while (leftChildNotThread(x))
x = x->left;
return x;
}
TNode* TBST::tree_maximum(TNode* x) // using recursion to find max
{
while (rightChildNotThread(x))
x = x->right;
return x;
}
void TBST::inOrderTraversal(TNode* x)
{
if (x != NULL)
{
if (leftChildNotThread(x))
inOrderTraversal(x->left);
printNode(x);
if (rightChildNotThread(x))
inOrderTraversal(x->right);
}
}
void TBST::preOrderTraversal(TNode* x)
{
if (x != NULL)
{
printNode(x);
if (leftChildNotThread(x))
preOrderTraversal(x->left);
if (rightChildNotThread(x))
preOrderTraversal(x->right);
}
}
void TBST::postOrderTraversal(TNode* x)
{
if (x != NULL)
{
if (leftChildNotThread(x))
postOrderTraversal(x->left);
if (rightChildNotThread(x))
postOrderTraversal(x->right);
printNode(x);
}
}
bool TBST::childrenNotThread(TNode* x)
{
return (x != NULL && rightChildNotThread(x) && leftChildNotThread(x));
}
bool TBST::rightChildNotThread(TNode* x)
{
return (x != NULL && x->right != NULL && x->right->parent == x);
}
bool TBST::leftChildNotThread(TNode* x)
{
return (x!= NULL && x->left != NULL && x->left->parent == x);
}
TNode* TBST::getMedian()
{
return this->median;
}
void TBST::updateMedian()
{
if (this->median != NULL)
{
//int half = int(ceil(((double)this->size) / 2.0));
if (this->smallerThanMedian < this->largerThanMedian)
{
this->median = tree_successor(this->median);
this->smallerThanMedian += 1;
this->largerThanMedian -= 1;
}
else if (this->smallerThanMedian > this->largerThanMedian)
{
this->median = tree_predecessor(this->median);
this->smallerThanMedian -= 1;
this->largerThanMedian += 1;
}
}
else
{
this->median = this->root;
this->smallerThanMedian = 0;
this->largerThanMedian = 0;
}
}
void TBST::removeSubTree(TNode* x)
{
if (x != NULL)
{
if (leftChildNotThread(x))
removeSubTree(x->left);
if (rightChildNotThread(x))
removeSubTree(x->right);
if (x->student_name != NULL)
{
delete x->student_name;
x->student_name = NULL;
}
delete x;
}
}
void TBST::printNode(TNode* x)
{
if (x != NULL && x->student_name != NULL)
{
std::cout << "ID: " << x->student_id << "\tName: " << *(x->student_name) << std::endl;
}
}
TBST::~TBST() // destructor
{
removeSubTree(this->root);
this->root = NULL;
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|