This is a simple binary search tree implementation written with C++'s templates feature I wrote to learn C++. What improvements would make this cleaner and better as far as C++ practices go, and are there any problems with implementing the algorithm?
#include <iostream>
#include <string>
using namespace std;
template <class T, class V>
class BinarySearchTree {
struct t_node {
t_node * parent;
t_node * left;
t_node * right;
T data;
V value;
// Sorted by Value
};
t_node * root;
t_node* getMin() {
return getMin(root);
}
t_node* getMin(t_node * x) {
while (x->left !=nullptr) {
x = x->left;
}
return x;
}
t_node* getMax() {
t_node * x = root;
while (x->right != nullptr) {
x = x->right;
}
return x;
}
t_node* sucessor(t_node* x) {
if (x->right != nullptr) {
return getMin(x->right);
}
t_node * y = x->parent;
while (y!=nullptr && x==y->right) {
x = y;
y = y->parent;
}
return y;
}
public:
void inOrderTreeWalk() {
inOrderTreeWalk(root);
}
// Needs Stream Overload on template T type to work.
void inOrderTreeWalk(t_node * x) {
if (x != nullptr) {
inOrderTreeWalk(x->left);
cout << x->data;
inOrderTreeWalk(x->right);
}
}
T search(V keyword) {
t_node * x = root;
while (x!=nullptr && keyword != x->value) {
if (keyword < x->value) {
x = x->left;
}
else x = x->right;
}
return x->data;
}
void insert(V keyword, T object) {
// Create t_node;
t_node * z = new t_node;
z->value = keyword;
z->data = object;
t_node * y = nullptr;
t_node * x = root;
while (x!= nullptr) {
y = x;
if (z->value < x->value) {
x = x->left;
}
else x = x->right;
}
z->parent = y;
if (y == nullptr) {
root = z;
} else if (z->value < y->value) {
y->left = z;
} else y->right = z;
}
};
// Demo Code
int main(int argc, const char * argv[]) {
string Charles = "Charles Finny";
string CharlesD = "Personal Assistant";
string Bob = "Bob of Yorkshire";
string BobD = "Unkown";
string Sam = "Sam Smith";
string SamD = "Programmer";
string Mary = "Mary Jane";
string MaryD = "Manager";
BinarySearchTree<string, string> EmployeeRecords;
EmployeeRecords.insert(Charles, CharlesD);
EmployeeRecords.insert(Bob, BobD);
EmployeeRecords.insert(Sam, SamD);
EmployeeRecords.insert(Mary, MaryD);
string result = EmployeeRecords.search("Sam Smith");
cout << result << "\n" ;
EmployeeRecords.inOrderTreeWalk();
return 0;
}
std::unique_ptr<t_node>
instead of the raw pointerst_node*
. \$\endgroup\$