code. compile. run. debug. share.
#include "TBST.h"
#include "functionality.h"
void insertToTree(TBST* tree, std::vector<std::string> args)
{
checkIfTreeIsInitialized(tree);
checkIfTreeIsEmpty(tree);
checkIfNumOfArguemntsIsThreeOrMore(args);
int id = returnID(tree);
std::string name = returnName(tree);
checkIfIdIsNum(id);
checkIfIdISOutOfRange(id);
insertElement(id, name);
}
void removeFromTree(TBST* tree, std::vector<std::string> args)
{
checkIfTreeIsInitialized(tree);
checkIfTreeIsEmpty(tree);
checkIfNumOfArguemntsIsTwo(args);
int id = returnID(tree);
checkIfIdIsNum(id);
checkIfIdISOutOfRange(id);
removeElement(id);
}
void searchInsideTree(TBST* tree, std::vector<std::string> args)
{
checkIfTreeIsInitialized(tree);
checkIfTreeIsEmpty(tree);
checkIfNumOfArguemntsIsTwo(args);
int id = returnID(tree);
checkIfIdIsNum(id);
checkIfIdISOutOfRange(id);
printSearch(id);
}
void findSuccessor(TBST* tree, std::vector<std::string> args) //fix the ID_INDEX
{
checkIfTreeIsInitialized(tree);
checkIfTreeIsEmpty(tree);
checkIfNumOfArguemntsIsTwo(args);
int id = returnID(tree);
checkIfIdIsNum(id);
checkIfIdISOutOfRange(id);
printSuccessor(id);
}
void findPredecessor(TBST* tree, std::vector<std::string> args) //fix the ID_INDEX
{
checkIfTreeIsEmpty(tree);
checkIfNumOfArguemntsIsTwo(args);
int id = returnID(tree);
checkIfIdIsNum(id);
checkIfIdISOutOfRange(id);
printPredecessor(id);
}
void findMinInTree(TBST* tree)
{
checkIfTreeIsInitialized(tree);
checkIfTreeIsEmpty(tree);
printMin(tree);
}
void findMaxInTree(TBST* tree)
{
checkIfTreeIsInitialized(tree);
checkIfTreeIsEmpty(tree);
printMax(tree);
}
void preTraversal(TBST* tree)
{
checkIfTreeIsEmpty(tree);
doPreorderTraversal(tree);
}
void inTraversal(TBST* tree)
{
checkIfTreeIsEmpty(tree);
doInorderTraversal(tree);
}
void postTraversal(TBST* tree)
{
checkIfTreeIsEmpty(tree);
doPostorderTraversal(tree);
}
void obtainMedian(TBST* tree)
{
checkIfTreeIsInitialized(tree);
checkIfTreeIsEmpty(tree);
printMedian(tree);
}
int main()
{
TBST* tree = new TBST();
cmdl* cmd = new cmdl;
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;
}
/* checking for possible errors and printing messages accordingly in addition to hiding functionality */
/* to continue - i must put the first functions into the latter to create nasted checkings */
#include "functionality.h"
void checkIfTreeIsEmpty(TBST* tree)
{
if (tree->root == nullptr)
{
std::runtime_error << "Given tree is empty. please add students' id and name into the tree" << std::endl; return ;
}
}
void checkIfTreeIsInitialized(TBST* tree)
{
if (tree == nullptr)
{
std::runtime_error << "The tree has not been intialized. it does not exist" << std::endl; return ;
}
}
void checkIfIdISOutOfRange(int id) /* to check */
{
catch (std::out_of_range& exception)
{
std::runtime_error<< "Given id is too large" << std::endl;
}
}
void checkIfIdIsNum(int id) /* to check */
{
catch (std::invalid_argument& exception)
{
std::runtime_error<< "Given ID should contain only digits" << std::endl;
}
}
void checkIfNumOfArguemntsIsThreeOrMore(std::vector<std::string> args)
{
if (args.size() < 3)
{
std::runtime_error<< "Please use Insert in addition to the students' id and name" << std::endl;
return;
}
}
void checkIfNumOfArguemntsIsTwo(std::vector<std::string> args)
{
if (args.size() != 2)
{
std::runtime_error << "please use Remove in addition to the id " << std::endl;
return;
}
}
void checkCorrectnessOfSearch(TBST* tree, std::vector<std::string> args)
{
if (args.size() != 2)
{
std::runtime_error << "please use search in addition to the id" << std::endl;
return;
}
}
bool checkIfExistsPredecessor(int id) /* if null then there's no predecessor */
{
TNode* node = tree->tree_predecessor(tree->search(id));
if (node!=nullptr) ? return true : return false;
}
bool checkIfExistsSuccessor(int id) /* if null then there's no successor */
{
TNode* node = tree->tree_successor(tree->search(id));
if (node!=nullptr) ? return true : return false;
}
void printPredecessor(int id) ///exists a problem because the boolean func only checks if true, otherwise it's *2 the num of operationss
{
int id1 = std::stoi(args[ID_INDEX]);
if(checkIfExistsPredecessor(id1))
{
std::cout << "The predeccessor of" << id << " is: " << node->s_Id << std::endl;
}
else{std::runtime_error<< "Predecessor does not exist"; std::endl;}
}
void printSuccessor(int id) //////exists a problem because the boolean func only checks if true, otherwise it's *2 the num of operationss
{
int id1 = std::stoi(args[ID_INDEX]);
if(checkIfExistsSuccessor(id1))
{
std::cout << "The successor of" << id1 << " is: " << node->s_Id << std::endl;
}
else{std::runtime_error<< "Successor does not exist"; std::endl;}
}
void printSearch(int id)
{
int id1 = std::stoi(args[ID_INDEX]);
TNode* node = tree->search(id1);
std::cout << "Students' name with the ID of" << id1 << " is: " << *(node->s_Name) << std::endl;
}
void removeElement(int id)
{
int id1 = std::stoi(args[ID_INDEX]);
tree->remove(id1);
}
void insertElement(int id, std::string name) //to verify
{
int id1 = std::stoi(args[ID_INDEX]);
std::string name = join(args, NAME_INDEX);
tree->insert(id1, name);
}
void printMin(TBST* tree)
{
int min = TBST::T_min(tree->root)->s_Id;
std::cout << "The Minimal student ID in the tree is: " << min << std::endl;
}
void printMax(TBST* tree)
{
int max = TBST::T_max(tree->root)->s_Id;
std::cout << "The Maximal student ID in the tree is: " << max << std::endl;
}
void printMedian(TBST* tree)
{
int median = tree->getMedian()->s_Id;
std::cout << "The median ID in the tree is: " << median << std::endl;
}
void doInorderTraversal(TBST* tree)
{
TBST::inOrderTraversal(tree->root);
}
void doPreorderTraversal(TBST* tree)
{
TBST::preOrderTraversal(tree->root);
}
void doPostorderTraversal(TBST* tree)
{
TBST::postOrderTraversal(tree->root);
}
void printHelp()
{
cmdl* cmd = new cmdl;
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 FUNCTIONALITY
#define FUNCTIONALITY
#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
void checkIfTreeIsInitialized(TBST*);
void checkIfTreeIsEmpty(TBST*);
void checkIfIdISOutOfRange(int);
void checkIfIdIsNum(int);
int returnID(TBST*);
std::string returnName(TBST*);
void checkIfNumOfArguemntsIsThreeOrMore(std::vector<std::string> args);
void checkIfNumOfArguemntsIsTwo(std::vector<std::string> args);
void checkCorrectnessOfSearch(TBST*, std::vector<std::string> args);
bool checkIfExistsPredecessor(int); /* if nullptr then there's no predecessor */
bool checkIfExistsSuccessor(int);
void printPredecessor(int);
void printSuccessor(int);
void printSearch(int);
void removeElement(int);
void insertElement(int, std::string name);
void printMin(TBST*);
void printMax(TBST*);
void printMedian(TBST*);
void doInorderTraversal(TBST*);
void doPreorderTraversal(TBST*);
void doPostorderTraversal(TBST*);
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";
} cmdl;
/*
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
#ifndef STRING
#define STRING
#include <string>
#endif
#ifndef MATH
#define MATH
#include <math.h>
#endif
#ifndef IOSTREAM
#define IOSTREAM
#include <iostream>
#endif
#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 = nullptr;
struct TNode* left = nullptr;
struct TNode* right = nullptr;
std::string* s_Name;
int s_Id;
} TNode;
class TBST /*an interface to implement all the neccesary commands from the handout */
{
public:
TBST();
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* T_predecessor(TNode*);
static TNode* T_successor(TNode*);
static TNode* T_min(TNode*);
static TNode* T_max(TNode*);
~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 */
};
#include "TBST.h"
TBST::TBST() //constructor
{
}
void TBST::insert(int id, std::string name)
{
if (name.empty()) {std::cout<<"no name was given"; return;}
TNode* x = this->root;
TNode* y = nullptr;
while (x != nullptr && x->parent == y)
{
y = x;
if (id < x->s_Id)
{
x = x->left;
}
else if (id > x->s_Id)
{
x = x->right;
}
else
return;
}
TNode* node = new TNode; //Initialization
node->s_Id = id;
node->s_Name = new std::string(name);
if (y == nullptr)
{
this->root = node;
}
else if (id < y->s_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 != nullptr)
{
if (id > this->median->s_Id)
this->largerThanMedian += 1;
else if (id < this->median->s_Id)
this->smallerThanMedian += 1;
}
updateMedian();
}
void TBST::remove(int id)
{
TNode* node = search(id);
if (node == nullptr)
return;
TNode* succ = T_successor(node);
TNode* pred = T_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 == nullptr)
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 != nullptr && node->parent->left == node)
node->parent->left = node->right;
else if (node->parent != nullptr && 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 != nullptr && node->parent->left == node)
node->parent->left = node->left;
else if (node->parent != nullptr && node->parent->right == node)
node->parent->right = node->left;
else
this->root = node->left;
pred->right = succ;
}
else
{
if (node->parent != nullptr && node->parent->left == node)
node->parent->left = pred;
else if (node->parent != nullptr && node->parent->right == node)
node->parent->right = succ;
else
this->root = nullptr;
}
if (node == this->root)
{
if (succ != nullptr)
this->root = succ;
else
this->root = pred;
}
this->size -= 1;
if (node == this->median)
{
if (succ != nullptr)
{
this->median = succ;
this->largerThanMedian -= (largerThanMedian > 0) ? 1 : 0;
}
else
{
this->median = pred;
this->smallerThanMedian -= (smallerThanMedian > 0) ? 1 : 0;
}
}
else
{
if (id > this->median->s_Id)
this->largerThanMedian -= (largerThanMedian > 0) ? 1 : 0;
else if (id < this->median->s_Id)
this->smallerThanMedian -= (smallerThanMedian > 0) ? 1 : 0;
}
updateMedian();
if (node->s_Name != nullptr)
{
delete node->s_Name;
node->s_Name = nullptr;
}
delete node;
}
TNode* TBST::search(int id)
{
TNode* x = this->root;
while (x != nullptr && id != x->s_Id)
{
if (id < x->s_Id)
{
if (leftChildNotThread(x))
x = x->left;
else
return nullptr;
}
else if (id > x->s_Id)
{
if (rightChildNotThread(x))
x = x->right;
else
return nullptr;
}
}
return x;
}
TNode* TBST::T_predecessor(TNode* x)
{
if (x == nullptr)
return nullptr;
if (x->left != nullptr && x->left->parent == x)
{
return T_max(x->left);
}
TNode* y = x->parent;
while (y != nullptr && x == y->left)
{
x = y;
y = y->parent;
}
return y;
}
TNode* TBST::T_successor(TNode* x)
{
if (x == nullptr)
return nullptr;
if (x->right != nullptr && x->right->parent == x)
{
return T_min(x->right);
}
TNode* y = x->parent;
while (y != nullptr && x == y->right)
{
x = y;
y = y->parent;
}
return y;
}
TNode* TBST::T_min(TNode* x) //using recursion to find min
{
while (leftChildNotThread(x))
x = x->left;
return x;
}
TNode* TBST::T_max(TNode* x) // using recursion to find max
{
while (rightChildNotThread(x))
x = x->right;
return x;
}
void TBST::inOrderTraversal(TNode* x)
{
if (x != nullptr)
{
if (leftChildNotThread(x))
inOrderTraversal(x->left);
printNode(x);
if (rightChildNotThread(x))
inOrderTraversal(x->right);
}
}
void TBST::preOrderTraversal(TNode* x)
{
if (x != nullptr)
{
printNode(x);
if (leftChildNotThread(x))
preOrderTraversal(x->left);
if (rightChildNotThread(x))
preOrderTraversal(x->right);
}
}
void TBST::postOrderTraversal(TNode* x)
{
if (x != nullptr)
{
if (leftChildNotThread(x))
postOrderTraversal(x->left);
if (rightChildNotThread(x))
postOrderTraversal(x->right);
printNode(x);
}
}
bool TBST::childrenNotThread(TNode* x)
{
return (x != nullptr && rightChildNotThread(x) && leftChildNotThread(x));
}
bool TBST::rightChildNotThread(TNode* x)
{
return (x != nullptr && x->right != nullptr && x->right->parent == x);
}
bool TBST::leftChildNotThread(TNode* x)
{
return (x!= nullptr && x->left != nullptr && x->left->parent == x);
}
TNode* TBST::getMedian()
{
return this->median;
}
void TBST::updateMedian()
{
if (this->median != nullptr)
{
//int half = int(ceil(((double)this->size) / 2.0));
if (this->smallerThanMedian < this->largerThanMedian)
{
this->median = T_successor(this->median);
this->smallerThanMedian += 1;
this->largerThanMedian -= 1;
}
else if (this->smallerThanMedian > this->largerThanMedian)
{
this->median = T_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 != nullptr)
{
if (leftChildNotThread(x))
removeSubTree(x->left);
if (rightChildNotThread(x))
removeSubTree(x->right);
if (x->s_Name != nullptr)
{
delete x->s_Name;
x->s_Name = nullptr;
}
delete x;
}
}
void TBST::printNode(TNode* x)
{
if (x != nullptr && x->s_Name != nullptr)
{
std::cout << "ID: " << x->s_Id << "\tName: " << *(x->s_Name) << std::endl;
}
}
TBST::~TBST() // destructor
{
removeSubTree(this->root);
this->root = nullptr;
}
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 |
|---|