bstree.hpp

#ifndef DSALAB_BSTREE_HPP
#define DSALAB_BSTREE_HPP

#include <cstdlib>

template<class T_>
struct Bst_node {
public:
typedef T_ value_type;

Bst_node* left;
Bst_node* right;
value_type data;

explicit Bst_node(const value_type& val = value_type())
: left(0), right(0), data(val) {}

Bst_node(const value_type& val, Bst_node* l, Bst_node* r)
: left(l), right(r), data(val) {}
};

template<class T_>
void destroy_tree(Bst_node<T_>* root)
{
if (0 == root)
return;
destroy_tree(root->left);
destroy_tree(root->right);
delete root;
}

template<class T_>
void insert(Bst_node<T_>*& root, const T_& val)
{
if (0 == root) {
root = new Bst_node<T_>(val);
return;
}

Bst_node<T_>* p = root;
for (; {
if (val < p->data) {
if (0 == p->left) {
p->left = new Bst_node<T_>(val);
return;
}
p = p->left;
}
else if (val > p->data) {
if (0 == p->right) {
p->right = new Bst_node<T_>(val);
return;
}
p = p->right;
}
else
return;
}
}

template<class T_>
void erase_root(Bst_node<T_>*& root)
{
if (0 == root)
return;

Bst_node<T_>* p = root;
if (0 == p->left)
root = p->right;
else if (0 == p->right)
root = p->left;
else {
Bst_node<T_>* p1 = p->right;
if (0 == p1->left) {
p1->left = p->left;
root = p1;
}
else {
Bst_node<T_>* p2 = p1->left;
while (p2->left != 0) {
p1 = p1->left;
p2 = p2->left;
}

p1->left = p2->right;

root = p2;
p2->left = p->left;
p2->right = p->right;
}
}

delete p;
}

template<class T_>
void erase(Bst_node<T_>*& root, const T_& val)
{
if (0 == root)
return;

Bst_node<T_>** pp = &root;
Bst_node<T_>* p;
for (; {
p = *pp;
if (val < p->data) {
if (0 == p->left)
return;
pp = &p->left;
}
else if (val > p->data) {
if (0 == p->right)
return;
pp = &p->right;
}
else {
erase_root(*pp);
break;
}
}
}

//----------------------------------------------------------------------------

template<class T_>
const Bst_node<T_>* find(const Bst_node<T_>* root, const T_& val)
{
if (0 == root)
return 0;

for (; {
if (val < root->data) {
if (0 == root->left)
return 0;
root = root->left;
}
else if (val > root->data) {
if (0 == root->right)
return 0;
root = root->right;
}
else
return root;
}
}

template<class T_>
bool contains(const Bst_node<T_>* root, const T_& val)
{ return find(root, val) != 0; }

template<class T_>
const Bst_node<T_>* min_node(const Bst_node<T_>* root)
{
if (0 == root)
return 0;

while (root->left != 0)
root = root->left;
return root;
}

template<class T_>
const Bst_node<T_>* max_node(const Bst_node<T_>* root)
{
if (0 == root)
return 0;

while (root->right != 0)
root = root->right;
return root;
}

template<class T_>
std::size_t height(const Bst_node<T_>* root, std::size_t h = 0)
{
if (0 == root)
return h;

const std::size_t lh = height(root->left, h + 1);
const std::size_t rh = height(root->right, h + 1);
return (lh > rh)? lh: rh;
}

//----------------------------------------------------------------------------

template<class T_>
class Bst_owner {
public:
typedef T_ value_type;

typedef Bst_node<value_type> node_type;

const node_type* root() const { return root_; }
node_type*& root() { return root_; }

// manipulator
void clear()
{
destroy_tree(root_);
root_ = 0;
}

Bst_owner& assign(node_type* root)
{
clear();
root_ = root;
return *this;
}

// accessor
bool empty() const { return 0 == root_; }

// ctor and dtor
Bst_owner(): root_(0) {}
~Bst_owner() { destroy_tree(root_); }
private:
node_type* root_;

// no copying allowed
Bst_owner(const Bst_owner&);
Bst_owner& operator=(const Bst_owner&);
};

#endif /* DSALAB_BSTREE_HPP */
















source.cpp

#include "bstree.hpp"

//----------------------------------------------------------------------------

template<class T_>
void erase_min(Bst_node<T_>*& root)
{
// TODO: do your work here


}

template<class T_>
void erase_max(Bst_node<T_>*& root)
{
// TODO: do your work here
}

template<class T_>
std::size_t count_at_depth(const Bst_node<T_>* root, std::size_t
depth)
{
// TODO: do your work here
return 0;
}

template<class T_>
std::size_t size(const Bst_node<T_>* root)
{
// TODO: do your work here
return 0;
}

//----------------------------------------------------------------------------

#include <ostream>

template<class T_>
void display_tree(
const Bst_node<T_>* root, std:stream& os, unsigned indent = 0)
{
if (0 == root)
return;
display_tree(root->left, os, indent + 1);
for (unsigned i = 0; i != indent; ++i)
os << " ";
os << root->data << "\n";
display_tree(root->right, os, indent + 1);
}

template<class T_>
void print_preorder(const Bst_node<T_>* root, std:stream& os)
{
if (0 == root)
return;
os << ' ' << root->data;
print_preorder(root->left, os);
print_preorder(root->right, os);
}

template<class T_>
void print_postorder(const Bst_node<T_>* root, std:stream& os)
{
if (0 == root)
return;
print_postorder(root->left, os);
print_postorder(root->right, os);
os << ' ' << root->data;
}

template<class T_>
void print_inorder(const Bst_node<T_>* root, std:stream& os)
{
if (0 == root)
return;
print_inorder(root->left, os);
os << ' ' << root->data;
print_inorder(root->right, os);
}

template<class T_>
void print_tree(const Bst_node<T_>* tree, std:stream& os)
{
using namespace std;
const size_t h = height(tree);
os << "size = " << size(tree) << ", height = "
<< h << " empty = " << (tree == 0);
if (tree != 0)
os << ", min = " << min_node(tree)->data
<< ", max = " << max_node(tree)->data;
os << '\n';

for (size_t i = 0; i < h; ++i)
os << "count_at_depth(" << i << ") = "
<< count_at_depth(tree, i) << '\n';

os << "\ninorder\n";
print_inorder(tree, os);
os << "\npreorder\n";
print_preorder(tree, os);
os << "\n----------" << endl;
}

//----------------------------------------------------------------------------

#include <iostream>
#include <vector>

#ifdef _MSC_VER
#ifdef _DEBUG
#include <crtdbg.h>
#endif
#endif

int main()
{
#ifdef _MSC_VER
#ifdef _DEBUG
// turn on memory leak checking
::_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif
#endif
using namespace std;

cout << boolalpha;

Bst_owner<int> tree_owner;
Bst_node<int>*& tree = tree_owner.root();

print_tree(tree, std::cout);

// add some elements
const int elements[] = { 4, 11, 8, 8, 27, 7, 5, 6, 15, 32, -5 };
const size_t num_elements = sizeof(elements) /
sizeof(elements[0]);
for (size_t i = 0; i < num_elements; ++i) {
cout << "inserting " << elements[i] << "\n";
insert(tree, elements[i]);
}

print_tree(tree, std::cout);

display_tree(tree, std::cout);

// search for some elements
const int test_elements[] = { 4, 8, 7, 5, 32, 31, 10, 2 };
const size_t num_test_elements
= sizeof(test_elements) / sizeof(test_elements[0]);
for (size_t i = 0; i < num_test_elements; ++i) {
cout << "contains " << test_elements[i] << "? ";
cout << contains(tree, test_elements[i]) << '\n';
}
cout << endl;

// remove some elements
const int elements_to_erase[] = { 32, 5, 6, 29, 16, 4 };
const size_t num_elements_to_erase
= sizeof(elements_to_erase) / sizeof(elements_to_erase[0]);
for (size_t i = 0; i < num_elements_to_erase; ++i) {
cout << "erasing " << elements_to_erase[i] << '\n';
erase(tree, elements_to_erase[i]);
}
cout << endl;

print_tree(tree, std::cout);

// search for some elements
for (size_t i = 0; i < num_test_elements; ++i) {
cout << "contains " << test_elements[i] << "? ";
cout << contains(tree, test_elements[i]) << '\n';
}
cout << endl;

// insert elements back
for (size_t i = 0; i < num_elements_to_erase; ++i) {
cout << "inserting " << elements_to_erase[i] << "\n";
insert(tree, elements_to_erase[i]);
}
cout << endl;

print_tree(tree, std::cout);

cout << "remove_max 5 times\n";
for (unsigned i = 0; i < 5; ++i) {
erase_max(tree);
}
print_tree(tree, std::cout);

cout << "remove_min 5 times\n";
for (unsigned i = 0; i < 5; ++i) {
erase_min(tree);
}

print_tree(tree, std::cout);
}