help me ! , about Binary Search Tree
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::ostream& 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::ostream& 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::ostream& 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::ostream& 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::ostream& 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);
}