help me ! , about Binary Search Tree

Discussion in 'C++' started by bushido, Jan 18, 2008.

  1. bushido

    bushido Guest

    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::eek: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::eek: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::eek: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::eek: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::eek: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 << "\n";
    insert(tree, elements);
    }

    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 << "? ";
    cout << contains(tree, test_elements) << '\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 << '\n';
    erase(tree, elements_to_erase);
    }
    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 << "? ";
    cout << contains(tree, test_elements) << '\n';
    }
    cout << endl;

    // insert elements back
    for (size_t i = 0; i < num_elements_to_erase; ++i) {
    cout << "inserting " << elements_to_erase << "\n";
    insert(tree, elements_to_erase);
    }
    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);
    }
    bushido, Jan 18, 2008
    #1
    1. Advertising

  2. 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::eek: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::eek: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::eek: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::eek: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::eek: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 << "\n";
    > insert(tree, elements);
    > }
    >
    > 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 << "? ";
    > cout << contains(tree, test_elements) << '\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 << '\n';
    > erase(tree, elements_to_erase);
    > }
    > 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 << "? ";
    > cout << contains(tree, test_elements) << '\n';
    > }
    > cout << endl;
    >
    > // insert elements back
    > for (size_t i = 0; i < num_elements_to_erase; ++i) {
    > cout << "inserting " << elements_to_erase << "\n";
    > insert(tree, elements_to_erase);
    > }
    > 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
    Jensen Somers, Jan 18, 2008
    #2
    1. Advertising

  3. bushido

    sassa Guest

    On Jan 18, 3:17 am, Jensen Somers <> 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 ;)
    sassa, Jan 23, 2008
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. brianm

    Binary search Tree:Help

    brianm, Jan 10, 2005, in forum: Java
    Replies:
    5
    Views:
    598
    Bjorn Abelli
    Jan 10, 2005
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,091
  3. Tarique Jawed

    binary search tree removal - stuck - HELP!!

    Tarique Jawed, Dec 6, 2003, in forum: C Programming
    Replies:
    4
    Views:
    410
    Ben Pfaff
    Dec 7, 2003
  4. tsunami
    Replies:
    3
    Views:
    331
    Mark P
    Aug 6, 2005
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,030
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page