c++ - 二叉搜索树

Question

我用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;

}

它编译得很好，但问题是:当我输入选择 1 时，它说输入要插入的数字，我输入例如 7，程序说:

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

为什么？出现这种问题的原因是什么？

Answer 1

在linux系统gdb下运行代码，报错是这样的:

Program received signal SIGSEGV, Segmentation fault.
0x080488ac in binary::insert (this=0xbffff33c, d=7) at so.cpp:52
52            if (t->data<parent->data)

在你的例子中，parent 是 NULL；这是因为在您的 empty() 方法中，您正在使用 root=NULL (将 root 设置为 NULL ) 而不是 root==NULL(检查 root 是否为 NULL)。