Sol Sol - 2 months ago 20
C++ Question

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

Answer

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