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);
}

Hello,

bushido wrote:
> 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);
> }
>

You don't really state what the problem is with this code. The only
thing I find are some TODO messages without further explanation of the
actual problem, which makes me believe this is some kind of homework
assignment. Nobody is going to do that for you.

- Jensen

On Jan 18, 3:17am, Jensen Somers <jensen.som...@gmail.com> wrote:
> > <snip>
>
> You don't really state what the problem is with this code. The only
> thing I find are some TODO messages without further explanation of the
> actual problem, which makes me believe this is some kind of homework
> assignment. Nobody is going to do that for you.
>
> - Jensen

I agree. If you cant manage this stuff in college/university your
going to drown in a real job