c++ - 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 element bool found=true; if (empty()){ cout<<"tree 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 leaf node // 2. we're removing node single child // 3. we're removing node 2 children // node 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 2 children //replace node 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 node's right child has left child // move way down left 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 choice : "; cin>>ch; switch(ch) { case 1: cout<<"enter number 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 deleted:"; cin>>tmp1; b.remove(tmp1); break; case 6: return 0; } } return 0; } it compiles fine problem it: when enter choice 1 enter number inserted enter example 7 , program says:
binary_tree exe has stopped working windows can check online solution problem check online solution , close program close program why?what reason when such kind of problem occurs?
running code under gdb on linux system, reported error:
program received signal sigsegv, segmentation fault. 0x080488ac in binary::insert (this=0xbffff33c, d=7) @ so.cpp:52 52 if (t->data<parent->data) in case, parent null; becase in empty() method, you're using root=null (setting root null) instead of root==null (checking if root null).
Comments
Post a Comment