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