Binary Search Tree Implementation(C++)

Question

Most of the code is from Weiss' "Data structures and algorithm analysis in C++", after I typed the code on CodeBlock(gnu,gcc), compiler reported no error, but then I tried to create an instance and test some functions it went wrong. It seems there's something wrong with BST() or insert() because the program stucked instantly since running. Would someone help me find out how to solve this problem?　Great thanks!!!

#include <iostream>
using namespace std;
struct TreeNode
{
    int element;
    TreeNode*left,*right;
    TreeNode(const int&e,TreeNode*le=NULL,TreeNode*rt=NULL):element(e),left(le),right(rt){};
};

class BST
{
public:
    BST(){root=NULL;};
    ~BST(){ makeEmpty(root); };
// use public member function to call private member functions.
    void insert(const int & x){ insert(x, root); }
    void remove(const int & x){ remove(x, root); }
    TreeNode*findMin() const{ return findMin(root); }
    bool contain(const int & x) const{ return contain(x,root); }
    void printNodes() const{ printNodes(root); }

private:
    TreeNode*root;

    void makeEmpty(TreeNode*&);
    TreeNode* findMin(TreeNode*) const;
    void insert(const int &, TreeNode*) const;
    void remove(const int &, TreeNode*) const;
    bool contain(const int &, TreeNode*) const;
    void printNodes(TreeNode*) const;
};

void BST::makeEmpty(TreeNode*&t)
{
    if(t!=NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t=NULL;
}
TreeNode* BST::findMin(TreeNode*t) const
{
    if(t->left==NULL)    return t;
    return findMin(t->left);
}
void BST::insert(const int & x, TreeNode* t) const
{
    if(t==NULL) t=new TreeNode(x,NULL,NULL);
    else if(x < t->element)    insert(x,t->left);
    else if(x > t->element)    insert(x,t->right);
    else;   /// duplicate, do nothing
}
void BST::remove(const int & x, TreeNode* t) const
{
    if(t==NULL) return;
    if(t->element > x)    remove(x, t->left);
    else if(t->element < x)  remove(x, t->right);
    else if(t->left!=NULL && t->right!=NULL)
    {
        t->element=findMin(t->right)->element;
        remove(t->element,t->right);
    }
    else
    {
        TreeNode*oldNode=t;
        t=(t->left==NULL)?t->right:t->left;
        delete oldNode;
    }
}
bool BST::contain(const int & x, TreeNode*t) const
{
    if(t==NULL)    return false;
    else if(x<t->element)    return contain(x,t->left);
    else if(x>t->element)    return contain(x,t->right);
    else    return true;
}
void BST::printNodes(TreeNode*t) const
{
    if(t==NULL) return;
    cout<<t->element<<" ";
    printNodes(t->left);
    printNodes(t->right);
    cout<<endl;
};

Here's the code I wrote to test class BST:

int main()
{
    BST BinarySearchTree;
    int element,node;
    for(int i=0; i<5; i++)
    {
        cin>>element;
        BinarySearchTree.insert(element);
    }
    BinarySearchTree.printNodes();

    cout<<BinarySearchTree.findMin()->element<<endl;

    cin>>node;
    if(BinarySearchTree.contain(node)){ cout<<"item "<<node<<" is in BST."<<endl; }

    BinarySearchTree.remove(node);
    BinarySearchTree.printNodes();
    return 0;
}

Not sure how insert, or remove are supposed to be const functions. They will certainly change the object at some point. You want your TreeNode defined like it is under makeEmpty. — pickypg
– pickypg, Commented Apr 25, 2013 at 5:51
Can you post the code wit which you test this BST? That will help me to run and see whats the issue.. — Raghuram
– Raghuram, Commented Apr 25, 2013 at 5:57
The code makes little sense. I don't think it can be fixed, it needs to be rewritten, and slowly. Typing lots of code from a book when you don't properly understand what you are doing is very unlikely to be a useful thing to do. Work more slowly. Start learning with something easier. — john
– john, Commented Apr 25, 2013 at 7:14
I changed the parameter Treenode* in private insert() and remove() to Treenode* & and it worked well. Thanks you guys~ — Sol
– Sol, Commented Apr 25, 2013 at 10:40

Drew Dormann · Accepted Answer · 2013-04-25 06:00:35Z

4

Your class BST has only one member variable. TreeNode*root. (There's no problem with that)

Your insert and remove functions presumably modify the BST, so you'll need to modify something relating to root.

(And your compiler will quickly point out that those functions shouldn't be const for the same reason.)

answered Apr 25, 2013 at 6:00

Drew Dormann

65.5k14 gold badges133 silver badges200 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

john · Accepted Answer · 2013-04-25 07:34:02Z

2

void BST::makeEmpty(TreeNode*&t)
{
    if(t==NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t=NULL;
}

This code is wrong, if t is NULL then you do t->left and t->right. That's called dereferencing a NULL pointer and is likely to make your program crash immediately.

This should be

void BST::makeEmpty(TreeNode*&t)
{
    if (t!=NULL)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t=NULL;
}

answered Apr 25, 2013 at 7:34

john

88.3k5 gold badges61 silver badges95 bronze badges

Comments

Elazar · Accepted Answer · 2013-04-25 06:05:12Z

1

You did nothing with root in insert(), so it does nothing (except for leaking memory).

answered Apr 25, 2013 at 6:05

Elazar

22k4 gold badges51 silver badges68 bronze badges

4 Comments

Sol Over a year ago

I did use a public member function insert() to call the private function insert(x, root)

Elazar Over a year ago

but root is passed by value, so the fact that you are changing t in the private function have no effect outside it.

Sol Over a year ago

Well I've changed the parameter Treenode* in private insert() to Treenode* &, guess this worked out then?

Elazar Over a year ago

I think it will. It will be super-ugly though. (implicit) pass by reference can easily make the calling code unreadable. BTW, don't take const int& parameters. there is no need for it. simple int is much better.

siddharth jain · Accepted Answer · 2014-07-20 14:29:11Z

0

if you want to cross-check your solution, you may find it here https://siddharthjain094.wordpress.com/2014/07/13/binary-search-tree-implementation-in-ccpp/

answered Jul 20, 2014 at 14:29

siddharth jain

212 bronze badges

1 Comment

Will Over a year ago

Can you post the code instead of linking to an outside site? That way in case the link dies, we still have the answer here.

Collectives™ on Stack Overflow

Binary Search Tree Implementation(C++)

4 Answers 4

Comments

Comments

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related