二分查找树

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为空；这是因为在您的empty()方法中，您使用的是root=NULL (将root设置为NULL)而不是root==NULL (检查root是否为NULL)。

Answer 2

问题出在这里：

bool empty()  { return root=NULL;}

更改为：

bool empty()  { return root == NULL;}

Answer 3

我看到的最明显的错误是您的empty实现实际上删除了树的根。它应该返回root == NULL的结果，而不是将NULL赋值给root (root=NULL)的结果。由于树实际上是空的，并且NULL等同于false，这会导致使用insert的"search“分支。由于current (和root)为NULL，因此parent永远不会被设置，并且当您尝试检查parent的数据值时，您会得到内存访问错误。

您可能还有其他错误，但这就是我所看到的。我建议您根据特定的场景为您的各个方法编写一些单元测试，以测试在该场景的条件下每个方法中会发生什么。如果您在编写足够的代码通过测试之前编写测试，这样会更好，这样您就知道当您的代码通过测试时它是正确的，并涵盖了测试场景，但您也可以在之后编写它们。如果您在之后编写代码，就很难知道您是否拥有所需的代码(并且不会有更多的代码)。在调试器失败时在调试器中运行这些测试(在这种情况下非常明显)有助于理解哪里出了问题，但是如果您使用测试作为指导缓慢地构建代码，您通常可以准确地指出没有错误的地方。