Reputation:
binary search tree
i have implement binary search tree in c++
#include <iostream>
#include <cstdlib>
using namespace std;
class binary{
private:
struct tree{
tree *left;
tree *right;
int data;
};
tree *root;
public:
binary(){
root=NULL;
}
bool empty() { return root=NULL;}
void print_inorder();
void inorder(tree*);
void print_preorder();
void pre_order(tree*);
void print_postorder();
void post_order(tree *);
void insert(int);
void remove(int);
};
void binary::insert(int d){
tree *t=new tree;
tree *parent;
t->data=d;
t->left=NULL;
t->right=NULL;
parent=NULL;
//is new tree;
if (empty()) root=t;
else{
tree *current;
current=root;
//find Nod's parent
while (current){
parent=current;
if (t->data>current->data) current=current->right;
else current=current->left;
}
if (t->data<parent->data)
parent->left=t;
else
parent->right=t;
}
}
void binary::remove(int d){
//locate the element
bool found=true;
if (empty()){
cout<<"tree is empty"<<endl;
return ;
}
tree *current;
tree *parent;
current=root;
while (current!=NULL){
if (current->data==d){
found=true;
break;
}
else{
parent=current;
if (d>current->data) current=current->right;
else current=current->left;
}
}
if (!found){
cout<<"data not found "<<endl;
return ;
}
//three case
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if ((current->left==NULL && current->right!=NULL )||(current->left!=NULL && current->right==NULL)){
if (current->left==NULL && current->right!=NULL){
if(parent->left==current){
parent->left=current->right;
delete current;
}
else{
parent->right=current->right;
delete current;
}
}
else // left child present, no right child
{
if (parent->left==current){
parent->left=current->left;
delete current;
}
else{
parent->right=current->left;
delete current;
}
}
return ;
}
if (current->left==NULL && current->right==NULL){
if (parent->left==current) parent->left=NULL;
else parent->right==NULL;
delete current;
return ;
}
//node with 2 children
//replace node with smalles value in right subtree
if ( current->left!=NULL && current->right!=NULL){
tree *ch;
ch=current->right;
if ((ch->left==NULL) &&(ch->right==NULL))
{
current=ch;
delete ch;
current->right=NULL;
}
else// right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if ((current->right)->left!=NULL){
tree * rr;
tree * lr;
lr=current->right;
rr=(current->right)->left;
while (rr->left!=NULL){
lr=rr;
rr=rr->left;
}
current->data=rr->data;
delete rr;
lr->left=NULL;
}
else
{
tree *tmp;
tmp=current->right;
current->data=tmp->data;
current->right=tmp->right;
delete tmp;
}
}
return;
}
}
void binary::print_inorder(){
inorder(root);
}
void binary::inorder(tree *p){
if (p!=NULL){
if (p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if (p->right) inorder(p->right);
}
else return ;
}
void binary::print_preorder(){
pre_order(root);
}
void binary::pre_order(tree *p){
if (p!=NULL){
cout<<" "<<p->data<<" ";
if (p->left) pre_order(p->left);
if (p->right) pre_order(p->right);
}
else return ;
}
void binary::print_postorder(){
post_order(root);
}
void binary::post_order(tree *p){
if (p!=NULL){
if (p->left) post_order(p->left);
if (p->right) post_order(p->right);
cout<<" "<<p->data;
}
else return ;
}
int main(){
binary b;
int ch,tmp,tmp1;
while (1){
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. In-Order Traversal "<<endl;
cout<<" 3. Pre-Order Traversal "<<endl;
cout<<" 4. Post-Order Traversal "<<endl;
cout<<" 5. Removal "<<endl;
cout<<" 6. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<"enter number to be inserted:";
cin>>tmp;
b.insert(tmp);
break;
case 2: cout<<endl;
cout<<"in order traversal"<<endl;
cout<<"------------------"<<endl;
b.print_inorder();
break;
case 3: cout<<endl;
cout<<"pre order traversal "<<endl;
cout<<"------------------"<<endl;
b.print_preorder();
break;
case 4: cout<<endl;
cout<<"post order traversal"<<endl;
cout<<"---------------------"<<endl;
b.print_postorder();
break;
case 5: cout<<"enter data to be deleted:";
cin>>tmp1;
b.remove(tmp1);
break;
case 6:
return 0;
}
}
return 0;
}
it compiles fine but problem is this it: when i enter choice 1 it say enter number to be inserted i enter for example 7 and program says:
binary_tree exe has stopped working
windows can check online for a solution to the problem
check online for a solution and close program
close program
why?what is reason when such kind of problem occurs?
Upvotes: 0
Views: 754
Answers (3)
Reputation: 532465
The most obvious error that I see is that your implementation of empty actually deletes the root of your tree. It should return the result of root == NULL rather than the result of the assignment of NULL to root (root=NULL). Since the tree is actually empty and NULL is equivalent to false, this causes the "search" branch of insert to be taken. Since current (and root) is NULL, parent never gets set and you get memory access error when you try to check the value of the parent's data.
You likely have other errors, but that's as far as I looked. I would suggest that you write some unit tests for your individual methods based on specific scenarios to test what happens in each under that scenario's conditions. It would be better if you wrote the test before you wrote just enough code to pass the test so that you knew that when your code passed the test it was correct and covered the test scenario, but you can write them afterwards as well. It's harder to know that you have exactly the code you need (and no more) if you write them afterwards. Running these test in the debugger when it fails (spectacularly, in this case) can be helpful to understand what is going wrong, but if you build the code up slowly using your tests as a guide, you can usually pin point where the error is without that.
Upvotes: 0
Reputation: 2307
Running the code under gdb on a Linux system, this is the reported error:
Program received signal SIGSEGV, Segmentation fault.
0x080488ac in binary::insert (this=0xbffff33c, d=7) at so.cpp:52
52 if (t->data<parent->data)
In your case, parent is NULL; this is becase in your empty() method, you're using root=NULL (setting root to NULL) instead of root==NULL (checking if root is NULL).
Upvotes: 4
Reputation: 13531
The problem is here:
bool empty() { return root=NULL;}
Change to:
bool empty() { return root == NULL;}
Upvotes: 1