CODEWITHSUNDEEP
c++data-structures
Sol
Sol

Reputation: 47

Binary Search Tree Implementation(C++)

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

Upvotes: 0

Views: 10408

Answers (4)

siddharth jain
siddharth jain

Reputation: 21

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/

Upvotes: 0

john
john

Reputation: 88027

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

Upvotes: 2

Elazar
Elazar

Reputation: 21685

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

Upvotes: 1

Drew Dormann
Drew Dormann

Reputation: 63946

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.)

Upvotes: 4

Related Questions