I have implemented a binary search tree using templates and unique_ptr in C++ 11. At present, only insertion and deletion are implemented. Please provide your feedback for improvements.
#include <iostream>
#include <memory>
template<typename T>
class Btree {
public:
void insert(T data)
{
_insert(root, data);
}
void traverse(void (*func)(T data))
{
_traverse(root, func);
}
void del(T data)
{
_del(root, data);
}
private:
struct node {
T data;
std::unique_ptr<node> left, right;
node(T data): data(data), left(nullptr), right(nullptr) {}
};
std::unique_ptr<node> root;
void _insert(std::unique_ptr<node>& curr, T data);
void _del(std::unique_ptr<node>& curr, T data);
void _traverse(std::unique_ptr<node>& curr, void (*func)(T data));
T _findmin(std::unique_ptr<node> &curr);
};
template<typename T>
void Btree<T>::_insert(std::unique_ptr<node>& curr, T data)
{
if (curr == nullptr) {
curr.reset(new node(data));
return;
}
if (data < curr->data)
_insert(curr->left, data);
else
_insert(curr->right, data);
}
template<typename T>
T Btree<T>::_findmin(std::unique_ptr<node>& curr)
{
if (curr && curr->left == nullptr)
return curr->data;
return _findmin(curr->left);
}
template<typename T>
void Btree<T>::_del(std::unique_ptr<node>& curr, T data)
{
if (curr == nullptr)
return;
if (data < curr->data)
_del(curr->left, data);
else if (data > curr->data)
_del(curr->right, data);
else {
// if one child is nullptr or both child are nullptr
if (curr->left == nullptr) {
auto &p = curr->right;
curr.reset(p.release());
}
else if (curr->right == nullptr) {
auto &p = curr->left;
curr.reset(p.release());
}
//if child is non leaf node
else {
T temp = _findmin(curr->right);
curr->data = temp;
_del(curr->right, temp);
}
}
}
template<typename T>
void Btree<T>::_traverse(std::unique_ptr<node>& curr, void (*func)(T data))
{
if (curr == nullptr)
return;
_traverse(curr->left, func);
func(curr->data);
_traverse(curr->right, func);
}